2.题目描述
给你一个字符串 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 <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-words-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
3.思路
1.首先我们可以先把字符串处理一下，把多个空格都变成一个空格。
2.然后我们要把字符串中的单词顺序反转，怎么才能做到只反转字符串中的一部分的顺序呢？我们这里可以先把整个字符串反转，这样每个单词的顺序就对了，但是每个单词都是反着的，所以我们再把每个单词的做一个反转就ok咯~
例子：
为了方便查看，我这里用_代替空格
s = ‘hello__world__a’
-> ‘hello_world_a’ # 去掉多余空格
-> ‘a_dlrow_olleh’ # 反转字符串
-> ‘a_dlrow_olleh_’ # 以空格来作为每个单词的结束标志
-> ‘a_world_hello_’ # 反转每个单词
4.代码实现
class solution:
def removeExtraSpaces(self, s: str):
result = '' # result: 用来保存结果
fast = 0 # fast: 当前位于s字符串中的第fast下标位
# 我们遇到多个空格的时候需要多次快进，所以这里不适合用for遍历字符串
# 而应该使用while才可以在遍历的过程中快进我们的下标
while fast < len(s):
# 当遇到多个空格时，我们需要判断下一个字符是否为空格，是则跳过
# 而且是连续跳过，所以使用while而不是if
while s[fast] == ' ' and fast + 1 < len(s) and s[fast+1] == ' ':
fast += 1
result += s[fast]
# 经过前面的while当前fast位置要么不是空格，要么下一个不是空格
# 也就是当前的fast位置不是连续的空格
fast += 1
# 这个地方可以直接return result[::-1]但是不建议这样做
# 因为这个方法的作用就是取出多余的空格，而没有反转的作用
# 方法的作用需要和方法的名字对应
return result
def reverseWords(self, s: str) -> str:
# 将字符串中的多个空格都变成一个
s = self.removeExtraSpaces(s)[::-1]
# 结果以上步骤，我们的s字符串已经在有空格的位置都保持了只有一个空格并且已经反转
# 所以接下里就是把每个单词都单独反转就可以了
# 显然我们需要遍历字符串，当遍历到空格的时候，就说明已经读取完毕某个单词
# 现在的s在前面和后面的可能有一个多余的空格
# 为了以空格为某个单词的结束标志
# 我们需要对s先预处理
# 保证s前面没有空格，最后一个位置有空格
if s[0] == ' ':
s = s[1:]
if s[-1] != ' ':
s += ' '
# 接下来就只需要以空格为分割标志，然后反转每个单词再拼接就ok咯
result = ''
slow = 0 # slow: 某个单词的启示下标
for fast in range(len(s)): # fast: 某个单词后的空格的下标
if s[fast] == ' ':
result += s[slow: fast][::-1] + ' '
slow = fast + 1
# 下一个单词的起始下标是fast+1而不是fast
# 因为fast指向的是空格
return result[:-1] # 再把s末尾的空格切掉就是答案了
4.性能分析
时间复杂度：O(n) 空间复杂度：O(n)
