151. Reverse Words in a String

https://leetcode.com/problems/reverse-words-in-a-string/

solution

• 直接

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

时间复杂度：O() 空间复杂度：O(n)

• 双指针

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.strip().split()
        left, right = 0, len(words) - 1

        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1
        return " ".join(words)

时间复杂度：O() 空间复杂度：O()

# TODO: no pass, for blank between and tail
class Solution:
    def reverseWords(self, s: str) -> str:
        s = list(s)
        start, end = 0, len(s) - 1
        self.help_reverse_word(s, start, end)
    
        start = end = 0    
        # Iterate over the string S
        while end < len(s):
            if s[end] == ' ':
                self.help_reverse_word(s, start, end - 1)
                start = end + 1
            end += 1
    
        # Reverse the words
        self.help_reverse_word(s, start, end - 1)
        return ''.join(s)
    
    def help_reverse_word(self, s, start, end):
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

时间复杂度：O(n) 空间复杂度：O(1)

follow up

186 Reverse Words in a String II

541. 反转字符串II

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        res = []
        flag = 0
        for i in range(0, len(s), k):
            substring = s[i: i+k]
            if flag % 2 == 0:
                res.append(substring[::-1])
            else:
                res.append(substring)
            flag += 1
        return "".join(res)