LeetCode 557. 反转字符串中的单词 III

2022-08-01 HGNULB 约 4 分钟

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

分类

LeetCode CodeTop 简单未解决 10-20 腾讯字节阿里微软美团百度快手携程猿辅导

题目描述

✅ 557. 反转字符串中的单词 III

题意分析

将字符串中每个单词内部的字符顺序反转，单词之间的排列顺序和空格位置保持不变。单词是由空格分开的连续字符段，空格本身不参与任何一段的反转。

只需改变每个单词内部的位置，不能把整个字符串倒过来，也不能在处理时合并、删除或移动分隔空格。

解法：逐词双指针反转

核心思路

[!blue]

不同单词占据互不重叠的字符区间，可以逐段独立反转。先把不可修改的字符串转换成字符或字节缓冲区，用 start 记录当前单词起点，扫描下标 i 负责寻找它的结束边界。

当 i 指向空格时，当前单词就是 [start, i)，传给反转函数的闭区间为 [start, i - 1]。左右指针在这段内部交换字符并向中间靠拢，空格不在区间中，因此它的位置始终不变。处理完后令 start = i + 1，从空格后开始寻找下一段。

最后一个单词后面没有空格，为了使用同一段处理逻辑，让扫描额外到达 i == length，把字符串末尾看作一个虚拟分隔位置。它不是真实字符，所以判断必须先写 i == length，再通过短路求值决定是否读取 chars[i]，避免越界。

每次处理后，start 之前的单词都已经完成，后面的字符仍待扫描。各段互不重叠且覆盖全部单词，因此逐段反转不会漏词，也不会改变词序。

解题步骤

把字符串转成可修改缓冲区，令 start = 0。

从左到右扫描 i，循环允许 i 等于缓冲区长度，作为最后一个单词的结束事件。

遇到空格或末尾时，用左右指针反转闭区间 [start, i - 1]。

将 start 更新为 i + 1，继续处理下一段。

全部单词完成后，将缓冲区转换回字符串并返回。

代码实现

class Solution {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int start = 0;

        for (int i = 0; i <= chars.length; i++) {
            // 把末尾视为分隔符，并先判断末尾来保护数组读取。
            if (i == chars.length || chars[i] == ' ') {
                // 只反转单词内部，分隔空格不参与交换。
                reverse(chars, start, i - 1);
                start = i + 1;
            }
        }

        return new String(chars);
    }

    private void reverse(char[] chars, int left, int right) {
        while (left < right) {
            char value = chars[left];

            chars[left] = chars[right];
            chars[right] = value;
            left++;
            right--;
        }
    }
}

func reverseWords(s string) string {
    chars := []byte(s)
    start := 0
    for i := 0; i <= len(chars); i++ {
        // 把末尾视为分隔符，并先判断末尾来保护数组读取。
        if i == len(chars) || chars[i] == ' ' {
            // 只反转单词内部，分隔空格不参与交换。
            reverseBytes(chars, start, i-1)
            start = i + 1
        }
    }
    return string(chars)
}

func reverseBytes(chars []byte, left int, right int) {
    for left < right {
        chars[left], chars[right] = chars[right], chars[left]
        left++
        right--
    }
}

复杂度分析

时间复杂度：$O(n)$。扫描和所有区间反转的总工作量都是线性的。

空间复杂度：$O(n)$。Java 和 Go 的字符串不可变，需要字符或字节数组保存结果。

关键点总结

[!green]

空格确定分段边界，反转只作用于每段内部，所以词序和空格位置自然保留。

用末尾虚拟分隔位置统一收尾，避免最后一个单词缺少处理时机。

先判断是否到末尾，再读取字符，利用短路保证数组访问合法。

易错点总结

[!yellow]

只扫描到 i < length 且没有额外收尾，最后一个单词不会遇到分隔符，因而漏掉反转。

把反转右端点写成 i，会把空格卷入单词；真正最后一个字符位于 i - 1。

先读取 chars[i] 再检查 i == length，虚拟分隔位置并没有对应字符，会越界。

处理完边界却不更新 start，下一次会重复反转前面的内容。

先整体反转再逐词反转，会得到词序颠倒的另一种变换。

Java 对字符数组调用 toString() 得不到字符内容，应使用 new String(chars)。

相似题目

题目	难度	关联与区别
151. 反转字符串中的单词	中等	本题保留单词顺序并反转各词内部，原题反过来保留词内字符而翻转单词顺序。
344. 反转字符串	简单	每个单词区间都可复用双指针反转，空格用于确定区间边界。
186. 反转字符串中的单词 II	中等	同系列。III 只反转词内字符；II 增加整体反转，将词内反转作为恢复单词顺序的子过程。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/77137837

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