LeetCode中等题之颠倒字符串中的单词

题目

给你一个字符串 s ，颠倒字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = “the sky is blue”
输出：“blue is sky the”
示例 2：

输入：s = " hello world "
输出：“world hello”
解释：颠倒后的字符串中不能存在前导空格和尾随空格。
示例 3：

输入：s = “a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，颠倒后的字符串需要将单词间的空格减少到仅有一个。

提示：

1 <= s.length <= 10^4
s 包含英文大小写字母、数字和空格 ’ ’
s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

来源：力扣（LeetCode）

解题思路

  可以直接利用python的过滤器和字符切片以及join完成题目要求。

class Solution:
    def reverseWords(self, s: str) -> str:
        s=list(filter(lambda x:x!='',s.split(' ')))
        s.reverse()
        return ' '.join(s)

  题目的进阶要求是需要原地进行操作，我们可以模拟刚才的函数，先对字符串进行去除多余的空格，然后在把整个字符串进行反转，最后遍历整个反转的字符串，针对单个单词再进行逐个反转。

class Solution:
    def reverseWords(self, s: str) -> str:
        s=s.strip()
        i,flag=0,1
        while i<len(s):
            while not flag and s[i]==' ':
                s=s[0:i]+s[i+1:]
            flag=1
            if flag and s[i]==' ':
                flag=0
            i+=1
        n=len(s)
        def swap(a,b,s):
            temp=s[a]
            s=s[0:a]+s[b]+s[a+1:]
            s=s[0:b]+temp+s[b+1:]
            return s
        for i in range(n//2):
            s=swap(i,n-1-i,s)
        temp,count='',0
        s+=' '
        for i in s:
            if i!=' ':
                temp=i+temp
            else:
                s=s[0:count-len(temp)]+temp+s[count:]
                temp=''
            count+=1
        return s[:-1]