0186. Reverse Words in a String II¶
题目信息¶
- 题号:
翻转字符串里的单词 II
- 难度:
Medium
- 主题:
数组、双指针、原地反转
- 原题:
- 重点:
用整体反转批量交换单词块,再按空格恢复每个单词内部顺序,全程复用字符数组
题目重述¶
给定字符数组 s,其中包含若干由单个空格分隔的单词,首尾没有空格。原地翻转单词顺序,
不能分配另一个与输入规模相关的数组。
单词内部字符顺序必须保持不变,空格仍作为相邻单词之间的单字符分隔符。接口直接修改
s,不返回新字符串。
自建示例¶
输入:['t','h','e',' ','s','k','y',' ','i','s',' ','b','l','u','e']
修改后:['b','l','u','e',' ','i','s',' ','s','k','y',' ','t','h','e']
即 "the sky is blue" 变为 "blue is sky the"。
输入:['a']
修改后:['a']
单个字符既是完整字符串也是唯一单词,两次反转后不变。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
public:
void reverseWords(std::vector<char>& s) {
std::reverse(s.begin(), s.end());
int size = static_cast<int>(s.size());
int word_start = 0;
for (int boundary = 0; boundary <= size; ++boundary) {
if (boundary == size || s[boundary] == ' ') {
std::reverse(
s.begin() + word_start,
s.begin() + boundary);
word_start = boundary + 1;
}
}
}
};
题解¶
额外数组方案保存了什么¶
最直接的方法是扫描出每个单词的起止位置,再从最后一个单词开始写入新数组。它正确, 但新数组复制了全部字符;若先切出独立字符串,还会额外保存单词列表。题目已经给出可写的 字符数组,原地要求提示我们寻找只靠区间交换改变块顺序的方法。
若反复把最后一个单词搬到数组前部,中间字符会被多次平移,最坏形成 O(n²) 工作。
需要一次全局操作同时改变所有单词块的相对顺序。
整体反转带来的两种变化¶
把整个字符数组反转,会同时发生:
单词块的排列顺序反转;
每个单词内部的字符顺序也反转。
例如:
原始: "the sky is blue"
整体反转: "eulb si yks eht"
第一种变化正是目标,第二种变化是副作用。空格字符虽然位置一起反转,但仍位于相邻反向 单词块之间,所以可以继续作为可靠边界。
逐词反转只撤销副作用¶
整体反转后,从左到右寻找空格。对每个不含空格的区间再次反转:
"eulb si yks eht"
↓ ↓ ↓ ↓
"blue is sky the"
第二轮只改变单词内部,不再交换单词块所在区间。因此“块顺序反转”被保留,“块内字符 反转”被执行两次而抵消,最终恰好只翻转单词顺序。
这里无需处理多余空格。题目保证单词间恰好一个空格、首尾无空格;与允许多空格并要求 规范化输出的版本不同,本题可以直接把每个空格当成确定分隔符。
边界扫描的状态¶
word_start 指向当前单词的首字符,boundary 扫描到空格或数组末尾。反转区间使用
C++ 左闭右开形式 [word_start, boundary),所以空格不参与单词内部反转。
条件先检查 boundary == size,借助逻辑或的短路规则,末尾哨兵轮不会访问
s[size]。处理完一个真实空格后,word_start = boundary + 1 跳到下一单词;处理
最后一个单词时 boundary == size,同一分支完成末尾区间,无需在循环外复制代码。
具体走读¶
对 "one two three":
整体反转得到
"eerht owt eno";第一个空格使区间
[0,5)反转,得到"three owt eno";第二个空格使
"owt"恢复为"two";boundary == size时恢复最后的"eno",结果为"three two one"。
每次完成区间后,不变量是:当前边界之前的所有单词已经按目标块顺序排列,且内部字符已 恢复;边界之后仍保持整体反转状态,等待逐词恢复。
正确性与复杂度¶
整体反转把第一个单词块移到最后、最后一个移到最前,并对所有块同样处理,因此块顺序完全 倒置。每个单词随后在其当前位置第二次反转,字符顺序恢复;空格不进入任何逐词区间,分隔 结构不变。故最终数组恰为原单词序列的逆序。
整体反转访问每个字符一次量级,逐词反转的区间互不重叠,总计再访问每个非空格字符一次,
时间复杂度为 O(n)。除下标外不创建随输入增长的容器,额外空间为 O(1),修改直接
发生在传入的 vector<char> 中。