LeetCode 剑指 Offer 58 - I. 翻转单词顺序
目录
题目描述
题意分析
给一个由若干单词和空格组成的字符串，要求把单词的先后顺序颠倒过来，单词内部的字符顺序保持不变。例如
the sky is blue变成blue is sky the。
真正的难点不在「颠倒」，而在题面里那几条关于空格的补充规定：输入可能有前导空格、尾随空格，单词之间也可能夹着多个连续空格；而输出必须是规范形式——不含前导和尾随空格，单词之间只用一个空格分隔。也就是说这道题一半考的是「怎么把词切出来」，另一半才是「怎么倒过来拼」。
「单词由非空格字符组成，中间不含空格」这条定义给出了明确的切分判据：扫描过程中只需要区分「当前字符是不是空格」，遇到空格就跳过，遇到非空格就一直走到下一个空格为止，走过的这一段就是一个完整单词。整个过程一趟线性扫描即可，不需要回头。
由于要按相反顺序输出，最自然的做法是从字符串末尾往前扫：先遇到的单词恰好是要先输出的。这样连「先收集再反转」都省了。
边界要盯住：字符串可能全是空格，此时应返回空串；只有一个单词时不能在两端多出空格；单词紧贴字符串开头或结尾时，向前扫描的下标会走到 -1，循环条件必须能接住。
解法：从右向左双指针扫描
核心思路
调用
split再反转单词数组可以快速完成，但会隐藏本题的空格处理。面试时更推荐手写扫描：逻辑可控，也省去单词数组。
关键观察有两点。其一，从右往左扫描时，遇到的单词顺序正好就是输出顺序，所以不需要额外的容器保存全部单词再反转，边扫边追加即可。其二，单词的边界完全由「空格 / 非空格」的切换点决定，用两个下标就能定位：
right停在单词的最后一个字符，left一路左移直到越过单词的第一个字符，那么[left+1, right]就是这个单词。
于是外层循环的每一轮固定做三件事：跳过右侧连续的空格 → 用
left找到当前单词的左边界 → 把[left+1, right]这段追加进结果。做完一轮把right挪到left，继续下一轮。
不变量：每轮外层循环开始时，
right之后（不含）的所有字符都已经处理完毕，结果缓冲区里恰好是那部分中全部单词的逆序规范拼接。跳空格保证了不会把空格误当成单词，left的左移保证了单词被完整取出，两者合起来维持不变量。
输出的空格规范化靠一个小技巧完成：只在追加单词之前、且缓冲区已经非空时才补一个空格。这样第一个单词前面不会有空格，最后一个单词后面也不会有，中间恰好每两个单词之间一个空格，三种边界一次性解决，不需要事后
trim。
解题步骤
right初始化为最后一个字符的下标，外层循环条件right >= 0：从右往左扫，使得先取出的单词就是先输出的，省掉一次整体反转。每轮先跳过空格：
while (right >= 0 && s[right] == ' ') right--：这一步统一吃掉尾随空格和单词之间的多余空格。循环里必须带right >= 0的守卫，否则全空格输入会一路减到负数后越界。跳完空格后若
right < 0就break：说明左侧只剩空格，直接结束，避免继续构造空区间。令
left = right，再while (left >= 0 && s[left] != ' ') left--：把left推到单词左边界的前一位（可能是空格，也可能是 -1）。用「越过一位再回退」的写法，比在循环里判断是否到头更简洁。拼接前先判缓冲区是否非空，非空才补一个空格：这一条同时解决了「首部不能有空格」「尾部不能有空格」「中间只能有一个空格」三件事，不需要最后再做一次
trim，也不会出现「先加空格再删掉」的冗余。追加子串
[left+1, right+1)：left已经越过了单词首字符，所以起点是left + 1；right指向单词末字符，半开区间的终点是right + 1。这两个 ±1 是本题最容易写错的地方。令
right = left进入下一轮：left处要么是空格、要么是 -1，交给下一轮开头的跳空格逻辑统一处理，不必在这里额外减一。返回缓冲区内容：全空格输入时缓冲区始终为空，自然返回空串，无需特判。
以
s = " a good example "为例：三轮依次取出example、good、a，缓冲区依次变为example、example good、example good a。最后只剩前导空格，跳过后结束。这个过程同时完成了逆序和空格规范化。
代码实现
class Solution {
public String reverseWords(String s) {
StringBuilder ans = new StringBuilder();
int right = s.length() - 1;
while (right >= 0) {
// 先吃掉尾随空格与单词之间的多余空格。
while (right >= 0 && s.charAt(right) == ' ') {
right--;
}
if (right < 0) {
break;
}
int left = right;
while (left >= 0 && s.charAt(left) != ' ') {
left--;
}
// 缓冲区非空才补分隔空格，首尾自然不会多出空格。
if (ans.length() > 0) {
ans.append(' ');
}
ans.append(s, left + 1, right + 1);
right = left;
}
return ans.toString();
}
}
func reverseWords(s string) string {
ans := make([]byte, 0, len(s))
right := len(s) - 1
for right >= 0 {
// 先吃掉尾随空格与单词之间的多余空格。
for right >= 0 && s[right] == ' ' {
right--
}
if right < 0 {
break
}
left := right
for left >= 0 && s[left] != ' ' {
left--
}
// 缓冲区非空才补分隔空格，首尾自然不会多出空格。
if len(ans) > 0 {
ans = append(ans, ' ')
}
ans = append(ans, s[left+1:right+1]...)
right = left
}
return string(ans)
}
复杂度分析
- 时间复杂度：$O(n)$。
right与left都只单调左移，两者合起来对每个字符至多访问常数次；追加操作的总字符数不超过原串长度。全程没有回退和重复扫描，也没有正则引擎的额外开销。- 空间复杂度：返回结果占 $O(n)$；若不计返回值，额外空间为 $O(1)$。相比「切分成数组再反转」，这里不保存全部单词。
关键点总结
- 倒序输出优先考虑倒序扫描，避免先收集再整体反转。
- 手写解析的固定骨架是「跳分隔符 → 找边界 → 取单词 → 推进指针」。
- 仅在结果非空时添加分隔空格，天然保证首尾无空格、单词间只有一个空格。
left停在单词左边界的前一位，截取区间必须是[left + 1, right + 1)。- 若输入改为可变字符数组且要求原地处理，可追答「整体反转、逐词反转、压缩空格」。
易错点总结
- 直接反转整个字符串：会把单词内部也反转，
blue变成eulb。- 用
split(" ")却不过滤空串：连续空格会产生空单词，拼接后仍有多余空格。- 跳空格时漏掉下标守卫：全空格输入会把指针减到 -1 后继续访问，导致越界。
- 截取边界写错：起点应为
left + 1，终点应为right + 1；前者错会带入空格，后者错会漏掉末字符。- 无条件添加分隔空格：容易在结果首尾留下空格；应在结果已非空时再添加。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 151. 反转字符串中的单词 | 中等 | 与本题同题，进阶要求在可变字符数组上做到 $O(1)$ 额外空间 |
| 186. 反转字符串中的单词 II | 中等 | 保证无多余空格但必须原地完成，用「整体反转 + 逐词反转」两步走 |
| 557. 反转字符串中的单词 III | 简单 | 只反转每个单词内部而保持单词顺序，恰好是本题的镜像要求 |
| 344. 反转字符串 | 简单 | 最基础的双指针原地反转，是上面几题「逐词反转」步骤的底层零件 |
| 541. 反转字符串 II | 简单 | 按固定步长分段决定反转与否，考察下标区间的边界计算 |
| 58. 最后一个单词的长度 | 简单 | 只需本题的第一轮扫描，用来单独练「跳尾随空格再定左边界」 |
| 71. 简化路径 | 中等 | 分隔符换成 / 且要处理 . 与 ..，切分之后还需用栈维护目录层级 |
| 8. 字符串转换整数 (atoi) | 中等 | 同为手写字符串解析，重点在状态划分与溢出判断而非顺序调整 |
| 443. 压缩字符串 | 中等 | 同样是「扫描分段 + 原地写回」，读写双指针分离的写法值得对照 |
| 补充题 11. 翻转URL字符串里的单词 | 中等 | 分隔符变成三字符的 %20，切分判据要按子串匹配而不是单字符比较 |