0186. Reverse Words in a String II

题目信息

题号:
  1. 翻转字符串里的单词 II

难度:

Medium

主题:

数组、双指针、原地反转

原题:

LeetCode 0186

重点:

用整体反转批量交换单词块,再按空格恢复每个单词内部顺序,全程复用字符数组

题目重述

给定字符数组 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":

  1. 整体反转得到 "eerht owt eno";

  2. 第一个空格使区间 [0,5) 反转,得到 "three owt eno";

  3. 第二个空格使 "owt" 恢复为 "two";

  4. boundary == size 时恢复最后的 "eno",结果为 "three two one"。

每次完成区间后,不变量是:当前边界之前的所有单词已经按目标块顺序排列,且内部字符已 恢复;边界之后仍保持整体反转状态,等待逐词恢复。

正确性与复杂度

整体反转把第一个单词块移到最后、最后一个移到最前,并对所有块同样处理,因此块顺序完全 倒置。每个单词随后在其当前位置第二次反转,字符顺序恢复;空格不进入任何逐词区间,分隔 结构不变。故最终数组恰为原单词序列的逆序。

整体反转访问每个字符一次量级,逐词反转的区间互不重叠,总计再访问每个非空格字符一次, 时间复杂度为 O(n)。除下标外不创建随输入增长的容器,额外空间为 O(1),修改直接 发生在传入的 vector<char> 中。