LeetCode 剑指 Offer 58 - I. 翻转单词顺序
题目描述
题意分析
将单词的先后顺序反转，单词内部的字符顺序保持不变，标点也作为所在单词的一部分保留。输出不含首尾空格，单词之间只放一个空格。
要先输出原串最后一个单词，因此可以直接从右向左寻找单词，每次取出完整片段，而不必先拆分全部单词或反转所有字符。
解法：从右向左双指针扫描
核心思路
[!blue]
right从字符串末尾开始。先向左跳过连续空格，让它停在尚未处理的最后一个单词末尾；如果已经小于0，说明没有单词可取，扫描结束。然后令
left = right，继续向左寻找空格或字符串边界。循环停止时，left指向单词前的空格，或者等于-1，所以完整单词位于半开区间[left+1, right+1)。扫描方向虽然向左，追加的仍是原字符串中的整段，因此不会改变单词内部的顺序。每次提取的都是剩余部分最右边的单词，依次追加就得到反转后的词序。取完后令
right = left，下一轮从当前单词左侧继续；指针不会向右退回，也不会遗漏任何单词。只有答案中已有单词时，才在新单词前添加一个空格。这样第一个单词前没有空格，任意两个单词间恰好一个空格，最后一个单词后也不需要再清理。原串中的多余空格都由跳过空格的过程处理。
解题步骤
- 建立结果缓冲区，令
right = s.length - 1。- 在
right >= 0的前提下跳过空格；若越过开头，直接结束。- 从
right向左移动left，直到遇到空格或到达-1，确定当前单词的边界。- 若结果非空，先追加一个空格；随后追加原串中的
[left+1, right+1)。- 令
right = left，重复处理剩余部分，最后返回结果。空字符串或全空格字符串都不会追加任何单词，结果为空串。
代码实现
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)$。指针只向左移动，每个字符被检查至多常数次；所有单词追加的总长度也不超过原串长度。
- 空间复杂度：$O(n)$。结果缓冲区及最终字符串需要线性空间，扫描指针只占常数空间。
关键点总结
[!green]
- 从右向左决定单词顺序，按原方向复制完整单词片段。
left已经越过词首，right仍在词尾，提取区间是[left+1, right+1)。- 跳过原串空格、按需插入一个空格，分别负责识别单词和规范输出间隔。
易错点总结
[!yellow]
- 直接反转所有字符，会连单词内部和标点位置一起反转。
- 必须先检查指针非负，再访问字符；空串、全空格以及没有前导空格的首个单词都可能使指针到达
-1。- 把提取区间写成
[left, right)，会包含单词前的空格并漏掉词尾字符。- 每取一个单词就无条件追加空格，会产生首尾多余空格；应只在已有结果和新单词之间追加。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 186. 反转字符串中的单词 II | 中等 | 单词顺序翻转目标相同，原题以可修改字符数组输入，要求原地完成。 |
| 58. 最后一个单词的长度 | 简单 | 同样需要先处理空格并定位单词边界，原题只关心最后一个词的长度。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！