LeetCode 151. 反转字符串中的单词
目录
题目描述
题意分析
输入是一个可能「很脏」的字符串：多余空格可能出现在三种位置——前导（
" hello"）、尾随（"world "）、单词之间（"hello world"中间不止一个空格）。输出规范有三条，缺一不可：单词顺序整体反转；结果中单词之间恰好一个空格；结果没有前导和尾随空格。
「单词」指连续的非空格字符，单词内部的字符顺序保持不变，只调整单词整体的先后顺序。
约束保证字符串中至少有一个单词，所以不必处理全空格输入返回什么的歧义；但空格清理本身仍是这道题一半的分量——它才是真正容易写错的地方。
解法：从右向左提取单词
核心思路
从字符串末尾向前扫描，依次跳过空格并截取完整单词，得到的顺序正好是目标顺序。只在结果非空时补一个空格，可同时去掉前导、尾随和连续空格。
解题步骤
- 指针从末尾开始，先跳过连续空格。
- 记录单词右端点，再向左找到单词左端点。
- 若结果非空，先追加一个空格，再追加当前单词。
- 重复扫描，直到指针越过字符串开头。
代码实现
class Solution {
public String reverseWords(String s) {
StringBuilder ans = new StringBuilder();
int i = s.length() - 1;
while (i >= 0) {
while (i >= 0 && s.charAt(i) == ' ') {
i--;
}
if (i < 0) {
break;
}
int end = i;
while (i >= 0 && s.charAt(i) != ' ') {
i--;
}
if (ans.length() > 0) {
ans.append(' ');
}
ans.append(s, i + 1, end + 1);
}
return ans.toString();
}
}
func reverseWords(s string) string {
ans := make([]byte, 0, len(s))
for i := len(s) - 1; i >= 0; {
for i >= 0 && s[i] == ' ' {
i--
}
if i < 0 {
break
}
end := i
for i >= 0 && s[i] != ' ' {
i--
}
if len(ans) > 0 {
ans = append(ans, ' ')
}
ans = append(ans, s[i+1:end+1]...)
}
return string(ans)
}
复杂度分析
- 时间复杂度：$O(n)$，指针只从右向左扫描一次。
- 空间复杂度：$O(n)$，用于构造返回字符串。
关键点总结
- 反向扫描可直接得到反转后的单词顺序，无需额外翻转。
- 每轮先跳空格，再提取单词，并在两个阶段都检查边界。
- 空格由结果主动添加，保证单词之间恰好一个空格。
易错点总结
- 跳过空格后未检查指针是否越界，会在前导空格处访问非法下标。
- 单词左端点应为
i + 1，右端点截取时应包含end。- 每个单词后都追加空格，会留下尾随空格。
- Java 使用字符串
+=反复拼接，最坏会退化为 $O(n^2)$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 186. 反转字符串中的单词 II | 中等 | 字符数组上原地整体反转加逐词反转 |
| 344. 反转字符串 | 简单 | 双指针原地交换的基本功 |
| 345. 反转字符串中的元音字母 | 简单 | 双指针只对满足条件的字符做交换 |
| 541. 反转字符串 II | 简单 | 按固定步长分段、段内选择性反转 |
| 557. 反转字符串中的单词 III | 简单 | 保持单词顺序、只反转单词内部 |
| 剑指 Offer 58 - I. 翻转单词顺序 | 简单 | 同一模型，输入可能全为空格的边界处理 |
| 补充题 11. 翻转URL字符串里的单词 | 中等 | 同一思路在 URL 场景下的工程化变体 |