0151. Reverse Words in a String
===============================
题目信息
--------
:题号: 0151. 反转字符串中的单词
:难度: Medium
:主题: 字符串、双指针、原地压缩、区间反转
:原题: `LeetCode 0151 `_
:重点: 先把空格规则归一化,再用整体反转改变单词顺序、逐词反转恢复单词内部顺序
题目重述
--------
给定字符串 ``s``,其中单词是连续非空格字符组成的最大片段。返回单词出现顺序完全反转后的字符串。输入
可能有前导、尾随和连续多个空格;输出只保留原单词,相邻单词间恰好一个空格,首尾没有空格。输入保证
至少含一个单词。
自建示例
--------
* ``" code reads clearly "`` 变为 ``"clearly reads code"``;
* ``"one"`` 仍为 ``"one"``,不产生额外空格;
* ``" a bc "`` 先规范为空格单一的 ``"a bc"``,再得到 ``"bc a"``,单词内部字符不能反转。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
#include
class Solution {
private:
std::string collectWordsThenJoin(const std::string& s) {
std::vector words;
const int length = static_cast(s.size());
for (int read = 0; read < length;) {
while (read < length && s[read] == ' ') {
++read;
}
if (read == length) {
break;
}
const int start = read;
while (read < length && s[read] != ' ') {
++read;
}
words.push_back(s.substr(start, read - start));
}
std::string result;
for (int index = static_cast(words.size()) - 1;
index >= 0;
--index) {
if (!result.empty()) {
result.push_back(' ');
}
result += words[index];
}
return result;
}
std::string compactAndReverse(std::string s) {
const int originalLength = static_cast(s.size());
int write = 0;
for (int read = 0; read < originalLength;) {
while (read < originalLength && s[read] == ' ') {
++read;
}
if (read == originalLength) {
break;
}
if (write > 0) {
s[write] = ' ';
++write;
}
while (read < originalLength && s[read] != ' ') {
s[write] = s[read];
++write;
++read;
}
}
s.resize(write);
std::reverse(s.begin(), s.end());
for (int start = 0; start < write;) {
int end = start;
while (end < write && s[end] != ' ') {
++end;
}
std::reverse(s.begin() + start, s.begin() + end);
start = end + 1;
}
return s;
}
public:
std::string reverseWords(std::string s) {
return compactAndReverse(std::move(s));
}
};
题解
----
原始方案:先把单词变成独立对象
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
最直接的 ``collectWordsThenJoin`` 扫描出每个最大非空格片段,放进 ``words``,再从数组末尾向前拼接。它
把“识别单词”“反转顺序”“规范空格”分成清晰步骤,正确性直接;代价是同时保存单词数组、各个子串和最终
字符串,额外存储与输入长度成正比。
题目返回字符串本身已经提供一块可写缓冲区。若能在其中先得到规范单词序列,再利用区间反转改变排列,就
不必保存单词列表。
第一阶段:读写指针只保留逻辑内容
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
``read`` 在原内容上跳过全部空格,再复制一个完整单词;``write`` 指向规范结果的下一个位置。除第一个单词
外,每写新单词前只写一个空格。扫描结束后把字符串缩到 ``write``,便同时删除了前导、尾随和重复空格。
循环开始处理某个单词时,``write`` 不会越过 ``read``:前面删除过的空格只会让写指针更靠左;两个单词
之间至少有一个已被 ``read`` 跳过的空格,所以先写规范分隔符也不会覆盖尚未读取的单词首字符。原地向前
复制因此安全。
这个阶段结束后的不变量是:``s[0..write-1]`` 恰好按原顺序包含所有单词,单词间一个空格,首尾无空格。
后续反转无需再判断多余空格。
两类反转怎样只改变单词顺序
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
整体反转规范字符串,会同时发生两件事:单词块顺序倒置,每个单词内部字符也倒置。第二次扫描以空格为界,
逐个反转每个单词区间,只恢复内部字符顺序,不改变块的位置。因此最终只剩单词顺序的反转。
.. code-block:: text
规范化: "code reads"
整体反转: "sdaer edoc"
逐词恢复: "reads code"
空格是单字符分隔符,整体反转后仍然位于两个反向单词块之间;逐词反转的区间不包含空格,所以输出继续满足
间隔规则。
逐词扫描的边界
~~~~~~~~~~~~~~
``start`` 指向当前单词首字符,``end`` 前进到空格或字符串末尾;``reverse(begin+start, begin+end)`` 使用
左闭右开区间。完成后令 ``start = end + 1`` 跳过分隔空格。最后一个单词使 ``end == write``,新的
``start`` 虽为 ``write + 1``,循环条件立即失败,不会解引用越界。输入至少有一个单词,所以压缩结果非空。
为什么不用逐个搬移单词
~~~~~~~~~~~~~~~~~~~~~~
若每次把最后一个单词移到输出前方,字符串中间插入会反复移动后续字符,最坏形成二次工作。整体反转把
所有单词块的位置一次性互换,逐词反转又只访问每个字符一次;没有任何单词需要单独跨越其他单词。
主解选择与复杂度
~~~~~~~~~~~~~~~~
公开入口采用原地压缩加两类反转。每个字符参与常数次扫描或交换,时间 ``O(n)``;在传入的返回字符串缓冲
上操作,除返回值自身外只用固定下标,工作空间 ``O(1)``。分词数组方案同为线性时间,但额外空间
``O(n)``,保留它作为题目规则的直观基线;主解利用反转结构删除了单词数组与拼接状态。