0186. Reverse Words in a String II ================================== 题目信息 -------- :题号: 0186. 翻转字符串里的单词 II :难度: Medium :主题: 数组、双指针、原地反转 :原题: `LeetCode 0186 `_ :重点: 用整体反转批量交换单词块,再按空格恢复每个单词内部顺序,全程复用字符数组 题目重述 -------- 给定字符数组 ``s``,其中包含若干由单个空格分隔的单词,首尾没有空格。原地翻转单词顺序, 不能分配另一个与输入规模相关的数组。 单词内部字符顺序必须保持不变,空格仍作为相邻单词之间的单字符分隔符。接口直接修改 ``s``,不返回新字符串。 自建示例 -------- .. code-block:: text 输入:['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"。 .. code-block:: text 输入:['a'] 修改后:['a'] 单个字符既是完整字符串也是唯一单词,两次反转后不变。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { public: void reverseWords(std::vector& s) { std::reverse(s.begin(), s.end()); int size = static_cast(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²)`` 工作。 需要一次全局操作同时改变所有单词块的相对顺序。 整体反转带来的两种变化 ~~~~~~~~~~~~~~~~~~~~~~~~ 把整个字符数组反转,会同时发生: * 单词块的排列顺序反转; * 每个单词内部的字符顺序也反转。 例如: .. code-block:: text 原始: "the sky is blue" 整体反转: "eulb si yks eht" 第一种变化正是目标,第二种变化是副作用。空格字符虽然位置一起反转,但仍位于相邻反向 单词块之间,所以可以继续作为可靠边界。 逐词反转只撤销副作用 ~~~~~~~~~~~~~~~~~~~~ 整体反转后,从左到右寻找空格。对每个不含空格的区间再次反转: .. code-block:: text "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`` 中。