Leetcode 557. reverse word III in string

Power button | 557. Invert the words in the string III

Title screenshot

Method 1 ： Use extra space

First set up a new list ans, Store the original string in the list after traversal, decomposition and inversion , Final reuse join() The function converts the list into a new string and returns .

Traversal methods ： Go through it from beginning to end , Set two pointers i and start.

Shilling start be equal to i, When there is no space i Add up ;

And then from start To i Start traversing and reverse in ans Fill the list with elements ;

When you encounter a space i Accumulate again , And in ans Add spaces to the list ;

Make start Again, it's equal to i, Then repeat the first step 、 And the second part continues to traverse the elements in reverse order , Until the outer layer traversal is completed . Then convert the list to a string .

This algorithm is equivalent to starting to fill in the front non space elements in reverse order after encountering spaces every time , Finally, the words that meet the requirements of the title are in reverse order , But the position of each word is sequential .

Python join() Method | Novice tutorial

    def reverseWords(self, s: str) -> str:
        n = len(s)
        ans=[]
        i = 0
        while i < n:
            start = i
            while i < n and s[i] !=" ":
                i += 1
            for p in range(start, i):
                ans.append(s[start + i - 1 -p])
            while i < n and s[i] ==" ":
                i += 1
                ans.append(" ")
        return "".join(ans)

  Complete test code

class Solution:
    def reverseWords(self, s: str) -> str:
        n = len(s)
        ans=[]
        i = 0
        while i < n:
            start = i
            while i < n and s[i] !=" ":
                i += 1
            for p in range(start, i):
                ans.append(s[start + i - 1 -p])
            while i < n and s[i] ==" ":
                i += 1
                ans.append(" ")
        return "".join(ans)

class main:
    a = Solution()
    s = "Let's take LeetCode contest"
    print(s)
    b=a.reverseWords(s)
    print(b)


if __name__ == '__main__':
    main()

 

Method 2 ： utilize python Of split() Function traversal slice inversion

Direct use of split() The function cuts the word out of the string and reverses , And then use it join() Function is combined into a new string to return .

Python3 split() Method | Novice tutorial

class Solution(object):
    def reverseWords(self, s):
        return " ".join(word[::-1] for word in s.split(" "))

Method 3 ： Two slices

You can also avoid traversal , Directly reverse with two slices .

s.split(" ") Slicing can cut strings into words , and s.split(" ")[::-1] You can reverse the order of words after cutting the string into words .

" ".join() You can turn the word list into a string , and " ".join()[::-1] You can invert the string that the word list is converted to .

therefore " ".join(s.split(" ")[::-1])[::-1] Two reversals of , You can invert the letters of each word in the string , But the order of words remains the same .

class Solution(object):
    def reverseWords(self, s):
        return " ".join(s.split(" ")[::-1])[::-1]

Or you can reverse the string first , Then reverse the order of each word .

class Solution(object):
    def reverseWords(self, s):
         return " ".join(s[::-1].split(" ")[::-1])