LeetCode 186. 反转字符串中的单词 II

约 9 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 华为 商汤
标签
字符串 双指针
目录

题目描述

✅ 186. 反转字符串中的单词 II

题意分析

给定一个字符数组 s，其中的单词以单个空格分隔，要求把单词的顺序整体反转，且必须原地完成，额外空间为 $O(1)$。函数没有返回值，结果直接体现在传入的数组上。

「原地 + $O(1)$ 空间」是这道题与 151 题最大的差别，也是全题唯一的难点。有了这条约束，「按空格切分成字符串列表、倒序拼接」这类做法全部作废——那需要 $O(n)$ 的额外存储。

输入形态被限制得很干净：没有前导空格、没有尾随空格、单词之间恰好一个空格。这意味着不需要做任何空白规整，可以放心地把「空格」当成单词的唯一分隔标志。

要注意反转的是单词序列，不是字符序列："the sky" 应变成 "sky the"，而不是 "yks eht"。单词内部的字符顺序必须保持原样。

边界有三处：只有一个单词时（无空格）结果应与原数组一致；最后一个单词的右边没有空格，切分时必须靠「走到数组末尾」这个条件来收尾；数组本身可能只有一个字符。

解法：翻转两次

核心思路

先想清楚目标与现状的差距。以 "the sky is blue" 为例，目标是 "blue is sky the"。

如果只做一次整体反转（把整个字符数组首尾颠倒），得到的是 "eulb si yks eht"。观察这个中间结果：单词的顺序已经完全正确了（blue, is, sky, the），但每个单词内部的字符被倒着写了。这个观察是整道题的转折点——一次全局反转把「宏观顺序」和「微观顺序」同时翻了，而我们只想翻宏观的。

于是补救办法显而易见：再把每个单词各自反转一次，把微观顺序翻回来。两次反转叠加，单词内部恢复原状，而单词之间的顺序只被翻了一次，正是想要的结果。这就是经典的「整体反转 + 局部反转」双翻转技巧。

形式化地说，全程依赖的性质是：对一个由若干块拼成的序列做整体反转，等价于「块的顺序反转」再加上「每块内部反转」；这两个操作互相独立，所以把后者再做一次就能抵消掉。同样的道理支撑着数组轮转（189 题）——那里是「反转前 $k$ 个、反转后 $n-k$ 个、再整体反转」。

反转本身用相向双指针原地交换即可，只需要一个临时变量，满足 $O(1)$ 空间。切分单词也不需要额外存储，只要用一个 start 变量记住当前单词的起点，扫描到空格或数组末尾时就知道一个单词结束了。

解题步骤

  • 第一步，对整个数组做一次反转 reverse(s, 0, s.length - 1)。这一步同时翻转了单词顺序和单词内部字符；单词顺序已经到位，接下来只需修复内部。
  • 第二步，用 start 记录当前单词的起始下标，从 $0$ 扫到 s.length（注意是闭区间，多扫一位）。多扫的那一位不是笔误：最后一个单词后面没有空格，只能靠「下标等于数组长度」这个虚拟的哨兵来触发收尾；否则最后一个单词永远不会被反转。
  • 循环体内判断 i == s.length || s[i] == ' '，两个条件用短路或串联，且 i == s.length 必须写在前面——否则会先执行 s[s.length] 造成越界。这个顺序依赖于逻辑或的短路求值，是本题最需要留神的一行。
  • 命中分隔点时执行 reverse(s, start, i - 1)，反转的是 [start, i-1] 这个左闭右闭区间，即当前单词的完整范围（i 指向的是空格或越界位置，不属于单词）。
  • 随后 start = i + 1，跳过这个空格，指向下一个单词的第一个字符。由于题目保证单词间恰好一个空格，加一正好落在下一个单词的开头。
  • 反转函数用相向双指针：l < r 时交换 s[l] 与 s[r]，然后 l++、r--。循环条件用严格小于，长度为奇数时中间那个字符不需要动，长度为 $0$ 或 $1$ 时循环一次都不进——后者恰好处理了单字符单词。
  • 无需返回值，所有修改都发生在传入的数组上。

以 s = ['t','h','e',' ','s','k','y']（即 "the sky"）走一遍：

第一步整体反转 $[0, 6]$：交换下标 0 与 6 得 y h e _ s k t（用 _ 表示空格）；交换 1 与 5 得 y k e _ s h t；交换 2 与 4 得 y k s _ e h t；此时 l = 3、r = 3，循环结束。数组是 "yks eht"——单词顺序已变成 sky, the，但两个单词都是倒着的。
第二步扫描，start = 0：
$i = 0, 1, 2$：字符是 y、k、s，都不是空格，不动作。
$i = 3$：s[3] 是空格，命中。反转 $[0, 2]$：交换下标 0 与 2 得 s k y。数组变成 "sky eht"。start = 4。
$i = 4, 5, 6$：字符是 e、h、t，不动作。
$i = 7$：等于 s.length，命中（注意这里若先求 s[7] 会越界，靠短路避免）。反转 $[4, 6]$：交换下标 4 与 6 得 t h e。数组变成 "sky the"。start = 8，循环结束。
最终数组是 "sky the"，正确。

再看单个单词的边界 s = ['a','b','c']：整体反转得 "cba"；扫描时只有 $i = 3$ 命中末尾哨兵，反转 $[0, 2]$ 得回 "abc"。两次反转互相抵消，结果与原数组一致——这正是「只有一个单词时顺序不变」的正确行为，而且不需要任何特判。

代码实现

class Solution {
    public void reverseWords(char[] s) {
        reverse(s, 0, s.length - 1);

        int start = 0;
        for (int i = 0; i <= s.length; i++) {
            if (i == s.length || s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
    }

    private void reverse(char[] s, int l, int r) {
        while (l < r) {
            char swapValue = s[l];
            s[l] = s[r];
            s[r] = swapValue;
            l++;
            r--;
        }
    }
}

func reverseWords(s []byte) {
    reverseBytes(s, 0, len(s)-1)

    start := 0
    for i := 0; i <= len(s); i++ {
        if i == len(s) || s[i] == ' ' {
            reverseBytes(s, start, i-1)
            start = i + 1
        }
    }
}

func reverseBytes(s []byte, l int, r int) {
    for l < r {
        s[l], s[r] = s[r], s[l]
        l++
        r--
    }
}

复杂度分析

  • 时间复杂度：$O(n)$，$n$ 为字符总数。第一次整体反转做 $n/2$ 次交换；第二次扫描遍历 $n + 1$ 个位置，其间对每个单词做一次反转，所有单词长度之和不超过 $n$，交换次数合计不超过 $n/2$。总共约 $2n$ 次基本操作，与单词个数无关。
  • 空间复杂度：$O(1)$。反转函数只用了 l、r 和一个交换用的临时字符；主函数只用了 start 与 i。全程在原数组上就地交换，没有创建任何字符串、列表或副本——这正是本题相对 151 题被单独出一道的意义所在。

关键点总结

  • 「块的顺序反转」可以用「整体反转 + 每块内部反转」两步无额外空间地实现。这条恒等式是原地重排类问题的通用武器，数组轮转、字符串旋转判定、矩阵转置后翻转都建立在它之上。
  • 两次反转的顺序可以互换（先逐词反转再整体反转，结果相同），但先整体后局部更好写——局部反转时单词边界已经在最终位置上，扫描逻辑更直白。
  • 扫描切分时给循环多留一位当哨兵，是处理「最后一段没有分隔符」的标准手法，比在循环后补一段收尾代码更不容易出错。
  • 短路求值的条件顺序是有语义的：i == s.length || s[i] == ' ' 中前者必须在前，否则越界。凡是把边界判断和取值判断写在同一个逻辑表达式里，都要检查这个顺序。
  • 面试视角：面试官出这题就是冲着 $O(1)$ 空间来的。上来要主动说明「不能切分成列表，那是 $O(n)$」，再讲双翻转恒等式。追问「如果单词间有多个空格、首尾有空格呢」，那就是 151 题——要么允许 $O(n)$ 空间用双指针边扫边写，要么原地先做空白规整（快慢指针压缩空格）再套双翻转。追问「与轮转数组有什么关系」，要能答出三次反转的公式。

易错点总结

  • 循环上界写成 i < s.length：s = "the sky" 时最后一个单词 eht 永远等不到分隔符触发反转，输出 "sky eht"，正确是 "sky the"。
  • 条件顺序写成 s[i] == ' ' || i == s.length：i 等于长度时先求 s[i] 直接数组越界抛异常。
  • 反转区间写成 reverse(s, start, i)：s = "the sky" 中第一次命中时会把空格也卷进去，反转 $[0, 3]$ 得到 " sky" 错位，最终输出的空格位置全乱。
  • 忘记第一次整体反转，只逐词反转：s = "the sky" 会输出 "eht yks"，单词顺序没变而内部被翻了，正好是想要结果的反面。
  • 只做整体反转不做逐词反转：输出 "yks eht"，单词顺序对了但每个单词都是倒的。
  • start 更新写成 start = i：下一个单词的起点落在空格上，s = "the sky" 第二次反转的区间变成 $[3, 6]$，把空格和单词一起翻转，输出 "skyeht " 这类空格移位的结果。
  • 反转函数循环条件写成 l <= r：l == r 时执行一次自我交换，虽然结果不变但多做了无谓操作；若写成 l != r 则在长度为偶数时两指针会错过相遇点，l 与 r 交叉后无限循环。
  • 用额外的 String[] 切分再拼回：s = "the sky" 结果虽然正确，但额外空间是 $O(n)$，违反题目约束，面试中直接被判不合格。
  • 误以为要反转字符：把 "the sky" 变成 "yks eht" 就返回，那是 344 题的做法，本题要反转的是单词序列。
  • 假设存在前导或尾随空格而做额外裁剪：题目保证没有多余空格，多写的裁剪逻辑在 s = "a" 这类输入上可能把唯一的字符误删。

相似题目

题目 难度 考察点
151. 反转字符串中的单词 中等 允许多空格与首尾空格，需先原地压缩空白再套双翻转，边界处理复杂得多
557. 反转字符串中的单词 III 简单 只反转每个单词内部而保持单词顺序，正是本题第二步单独拿出来
344. 反转字符串 简单 相向双指针原地反转的最简形态，是本题反转函数的本体
189. 轮转数组 中等 三次反转实现循环右移，与本题共用「整体反转加局部反转」的恒等式
541. 反转字符串 II 简单 按固定步长分块反转，切分依据是下标而非分隔符，考区间边界的取舍
345. 反转字符串中的元音字母 简单 双指针跳过非目标字符再交换，反转的是筛选出的子序列
48. 旋转图像 中等 二维原地旋转，用「转置 + 每行反转」实现，是本题恒等式的矩阵版本
796. 旋转字符串 简单 判断能否通过轮转互相得到，用 $s+s$ 包含判定，与原地重排互为反问