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

约 5 分钟
文章信息 13 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度
标签
字符串 双指针
目录

题目描述

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

image-20230306230547617

题意分析

输入一个字符串，要求把每个单词内部的字符顺序颠倒过来，而单词之间的先后顺序、以及空格所在的位置都保持不变。比如 God Ding 要变成 doG gniD，而不是整句倒过来的 gniD doG。

约束里给了两个很关键的信号。一是字符串只包含英文字母和空格，不含标点和多字节字符，所以可以放心按字节／字符逐个处理，不必担心把一个字符拆成两半；二是题目保证不存在前导或尾随空格，且两个单词之间只有一个空格。第二点意味着「按空格切分」得到的每一段都是非空单词，也意味着输出串的长度、每个空格的下标都与输入完全一致——既然位置不变，就没有必要重新排布，只需在原位置上把每段字母翻过来。

边界要留意：整个串可能只有一个单词，此时全程遇不到空格，最后那段单词的反转只能靠「扫描到末尾」这个事件来触发；单词也可能只有一个字母，反转它等于什么都不做，双指针要能自然处理这种空转情况。

解法：逐词双指针反转

核心思路

单词顺序和空格位置都不变，说明每个单词可以独立处理。把字符串转成可修改的字符数组，用 start 记录当前单词起点；扫描到空格或字符串末尾时，用双指针反转区间 [start, i - 1]。

为统一处理最后一个单词，让扫描下标走到 i == length。条件 i == length || chars[i] == ' ' 利用短路求值避免越界，同时把末尾当作一个虚拟分隔符，不必在循环后重复调用反转函数。

循环不变量是：每轮开始时，start 之前的所有单词都已正确反转，空格位置未改变，start 指向当前未处理单词的首字符。遇到边界后反转当前单词并令 start = i + 1，不变量继续成立；扫描结束时所有单词均已处理。

解题步骤

  • 将字符串转为可修改的字符数组，初始化 start = 0。
  • 从左向右扫描，下标走到数组长度（含）以触发最后一次处理。
  • 遇到空格或末尾时，双指针反转 [start, i - 1]。
  • 更新 start = i + 1，继续定位下一个单词。
  • 将字符数组转回字符串。

例如 God Ding 在空格处先把 God 反转为 doG，扫描到末尾时再把 Ding 反转为 gniD，得到 doG gniD，空格始终留在原下标。

代码实现

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 的字符串不可变，需要字符或字节数组保存结果；若输入本身是可变字符数组，额外空间可降为 $O(1)$。

关键点总结

  • 只反转单词内部，不能改变单词顺序或空格位置。
  • 扫描到 length 能把末尾与空格统一为边界事件，避免漏掉最后一个单词。
  • 反转的右端点是 i - 1，分隔符不属于单词。
  • Go 按字节处理成立的前提是题目只含英文字母；若允许 Unicode，应改用 []rune。

易错点总结

  • 循环只写到 i < length 会漏掉最后一个单词；必须额外收尾或扫描到 i == length。
  • 反转 [start, i] 会把空格卷入单词，正确区间是 [start, i - 1]。
  • 边界后忘记把 start 更新为 i + 1，下一轮会从空格开始反转。
  • Java 返回 chars.toString() 得到的是数组标识，不是字符内容，应使用 new String(chars)。
  • 先整体反转再逐词反转是 151 题的思路，会改变本题要求保持不变的单词顺序。

相似题目

题目 难度 考察点
151. 反转字符串中的单词 中等 多余空格清理加整体反转
186. 反转字符串中的单词 II 中等 严格原地、$O(1)$ 空间
344. 反转字符串 简单 相向双指针基本功
345. 反转字符串中的元音字母 简单 带筛选条件的交换
541. 反转字符串 II 简单 按固定步长分段反转
剑指 Offer 58 - I. 翻转单词顺序 简单 单词顺序整体倒置
补充题 11. 翻转URL字符串里的单词 中等 自定义分隔符切分