[数据结构与算法]Leetcode 151.颠倒字符串中的单词 Reverse Words in a String - Python 双指针法

class Solution:
    def reverseWords(self, s: str) -> str:
        def trim_space(s:str):
            res = []
            front = 0
            rear = len(s)-1
            while s[front] == ' ':
                front += 1
            while s[rear] == ' ':
                rear -= 1
            while front <= rear:
                if s[front] != ' ':
                    res.append(s[front])
                elif res[-1] !=' ':   #当前数组最后一个元素为字母
                    res.append(s[front])
                front += 1
            return res
        
        def reverseString(nums,front,rear):
            while front < rear:
                nums[front], nums[rear] = nums[rear], nums[front]
                front += 1
                rear -= 1
            return nums

        def reverseSingleWords(nums):
            front, rear = 0, 0
            n = len(nums)
            while front < n:   #遍历整个字符数组
                while rear < n and nums[rear] != ' ':  #定位到一个单词的末尾字母
                    rear += 1
                reverseString(nums,front,rear-1) #用front和rear指针将一个单词框起来 然后颠倒
                front = rear + 1
                rear += 1
            return nums

        ans = trim_space(s)
        reverseString(ans,0,len(ans)-1)
        reverseSingleWords(ans)
        return ''.join(ans)

思路：

1.去掉多余的空格

2.将整个字符串颠倒

3.分别将每个单词颠倒

时间复杂度为O(n)