Reverse Words in a String
给你一个由单词和空格组成的字符串 s。单词是由字母和数字组成的一段连续字符，其中不包含空格。单词之间可能有多个空格，s 的开头或结尾也可能有空格。
按相反顺序返回这些单词，用且仅用一个空格连接，开头和结尾都不留空格。每个单词的拼写保持不变，只改变单词的顺序。
函数
- sstring
- 至少包含一个单词的字母、数字和空格
- 返回值string
- s 中的单词按相反顺序排列，并用单个空格分隔
约束条件
1 ≤ s.length ≤ 104s只包含英文字母、数字和空格。s至少包含一个单词。
示例
- 输入
- s = "Coddy runs in 15 languages"
- 输出
- "languages 15 in runs Coddy"
- 解释
- 这些词是
Coddy、runs、in、15和languages。从后往前读，它们组成languages 15 in runs Coddy；15算作一个词，因为词中可以包含数字。
- 输入
- s = " practice makes progress "
- 输出
- "progress makes practice"
- 解释
- 两端的空格会被删除，单词之间连续的两个或三个空格会缩减为一个。三个单词按从后到前的顺序输出：
progress makes practice。
- 输入
- s = " single "
- 输出
- "single"
- 解释
- 由一个单词组成的列表，反过来读也一样。只有单词前后的空格会消失，所以答案是
single。
进阶
你能把单词倒序排列，同时保留 s 的空格吗：空格段的数量、长度和顺序都保持不变？
提示
逐个打开提示，每个都会多透露一点。
先暂时不考虑空格。如果这些单词已经在一个列表里，你会怎样拼出答案？然后想一想，额外的空格会怎样影响把字符串拆分成单词这一步。
按空格拆分，并删除连续两个空格或首尾空格产生的空项。将单词列表反转，再用单个空格连接。
如果要在一个字符数组中直接操作，可以反转整个数组，这样单词的顺序就正确了，但每个单词都变成了反着拼写。然后再反转每个单词，并用第二个索引向前复制其中的字符，这样每段连续的空格都会缩减为一个。
题解
单词顺序需要反转；空格处理不当会导致答案出错。开头和结尾的空格，以及单词之间重复的空格都必须去掉，答案中单词之间必须恰好有一个空格。你可以把字符串拆分成单词列表，也可以先反转整个字符串，再反转同一个数组中的每个单词。
拆分成单词，并按相反顺序将它们连接起来
思路
把 s 拆分成单词，反转列表，然后用单个空格将它们连接起来。拆分时要小心：在每个空格处拆分 " practice makes progress "，会在这三个单词周围得到六个空字符串。去掉空字符串后，列表中就是 practice、makes、progress。
拆分时会读取每个字符一次，连接时会写入每个保留的字符一次，因此对于长度为 n 的字符串，时间复杂度为 O(n)。单词列表和答案需要 O(n) 的额外空间。
算法
- 按空格拆分
s。 - 删除空字符串片段。
- 反转单词列表。
- 用一个空格连接每个单词，并返回结果。
def reverseWords(s):
# split() with no argument treats any run of spaces as one separator
# and ignores spaces at both ends.
words = s.split()
words.reverse()
return " ".join(words)先反转整个字符串，再反转其中的每个单词
思路
反转整个字符串后，单词顺序是正确的，但每个单词都拼反了：Coddy runs in 15 languages 会变成 segaugnal 51 ni snur yddoC。再单独反转每个单词，就会得到 languages 15 in runs Coddy。
空格也在同一遍处理中。read 索引遍历反转后的数组并跳过空格；write 索引标记下一个保留字符的写入位置。复制时不会覆盖仍需使用的字符，因为 write 永远不会超过 read：在单词前写入的一个空格，代表 read 跳过的至少一个空格。
每个字符最多复制一次，最多交换两次，因此时间复杂度为 O(n)；对于可修改的字符缓冲区，额外空间复杂度为 O(1)。这里的字符串以值的形式传入，因此每个答案都会为 s 创建一个工作副本：总内存为 O(n)。
算法
- 将
s复制到字符数组中，然后反转整个数组。 - 使用读取索引遍历数组，并跳过空格。
- 处理每个单词时，如果它不是第一个单词，就先写入一个空格，然后将单词的字符复制到写入索引处。
- 反转你复制的那段字符，让单词正向显示。
- 返回前
write个字符。
def reverseWords(s):
chars = list(s)
def reverse(lo, hi):
while lo < hi:
chars[lo], chars[hi] = chars[hi], chars[lo]
lo += 1
hi -= 1
n = len(chars)
reverse(0, n - 1) # words in the right order, each spelled backwards
write = 0
read = 0
while read < n:
if chars[read] == " ":
read += 1
continue
if write > 0:
chars[write] = " " # one space before every word but the first
write += 1
start = write
while read < n and chars[read] != " ":
chars[write] = chars[read]
write += 1
read += 1
reverse(start, write - 1) # spell the word forwards again
return "".join(chars[:write])
易错点和边界情况
- 按单个空格拆分，并保留每一部分。
"a b"会拆分成a、一个空部分和b，拼接后会还原为两个空格："b a"。 - 以为拆分会丢弃首尾部分。Java 的
split(" ")会丢弃末尾的空部分，但会保留开头的空部分，所以" a b"仍会留下一个空部分。 - 在每个单词后都添加一个空格，包括最后一个单词，因此答案会以空格结尾。应在每个单词前添加空格，第一个单词除外。
- 原地版本只反转一次。只反转单词会得到
yddoC snur ni 51 segaugnal。 - 在 PHP 和 R 中，像
2026这样的纯数字输入可能会以数字形式传入。拆分前，先将它转换为字符串。
常见问题3
反转字符串中的单词的时间复杂度是多少？
对于长度为 n 的字符串，两种方法的运行时间都是 O(n)，因为每个字符都会被读取和写入常数次。拆分操作需要使用 O(n) 的额外空间来存放单词列表。先反转整个字符串，再反转每个单词，在可修改的字符数组上只需要 O(1) 的额外空间。
如何处理单词之间的多个空格？
把一个单词视为一串不含空格的字符，并且不要复制输入中的空格。在 Python 和 Ruby 中，不带分隔符的 split、Go 中的 strings.Fields 和 Rust 中的 split_whitespace 已经会跳过所有连续空格以及两端的空格；其他情况下，丢弃空片段。然后在单词之间写入一个空格。
你能不使用 split 函数来反转单词吗？
是的。从右端开始扫描：跳过空格，标记单词的结尾，向左移动到单词的开头，然后在单词前加一个空格并追加该单词，除非它是第一个单词。每个字符只访问一次，因此时间复杂度仍为 O(n)，单词会以相反的顺序排列，而且不需要反转列表。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def reverseWords(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "Coddy runs in 15 languages"
预期输出
"languages 15 in runs Coddy"