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

2023-07-05 HGNULB 约 4 分钟

文章信息 8 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决会员题 2-5 华为商汤

题目描述

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

题意分析

原地反转字符数组中的单词顺序，词内字符保持不变。输入没有首尾空格，词间恰好一个空格。

解法：翻转两次

核心思路

[!blue]

一次整体反转会同时改变两种顺序：单词块的排列顺序和每个单词内部的字符顺序。再单独反转每个单词，词内字符就恢复原顺序，而各单词块不跨越空格移动，因此词序仍保持反转后的状态。

反转区间使用左右指针交换首尾字符，交换后同时向中间移动，直到两指针相遇或交错。它只修改原字符数组，整个算法也只需要几个下标和交换变量，满足原地操作要求。

整体反转后，用 start 记录当前单词起点。扫描到空格时，单词占据闭区间 [start, i-1]，反转它，再令 start = i+1。最后一个单词后没有空格，所以循环还要处理 i == length，把数组末尾视作虚拟分隔符；判断末尾必须放在读取 s[i] 之前，利用短路避免越界。

解题步骤

用双指针反转整个区间 [0, length-1]。

初始化 start = 0，扫描下标 i 从 0 到 length，包含末尾位置。

遇到空格或末尾时，反转 [start, i-1]，不把空格包括在内。

将 start 更新为 i+1，继续处理后续单词；数组修改完成后无需另建结果。

代码实现

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。

空间复杂度：$O(1)$，仅交换与边界变量。

关键点总结

[!green]

整体反转改变两种顺序，局部再反一次只恢复词内顺序。

最后一词没有真实分隔符，需要末尾结算。

易错点总结

[!yellow]

循环不到长度位置，最后一词无法恢复。

先读取长度位置再判断末尾，会越界。

局部区间包含空格，会移动词边界。

相似题目

题目	难度	关联与区别
151. 反转字符串中的单词	中等	单词顺序目标相同，本题输入可变字符数组并要求原地操作，原题可以构建新字符串。
344. 反转字符串	简单	整体反转再逐词反转可复用双指针原地反转字符区间。
557. 反转字符串中的单词 III	简单	同系列。II 整体反转后再逐词反转以恢复词内顺序；III 只进行逐词的局部反转。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/32047550

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！