LeetCode 151. 反转字符串中的单词

约 5 分钟
文章信息 22 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 100-200 LeetCode 75 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 百度 网易 快手 滴滴 虾皮 猿辅导
标签
字符串 双指针

题目描述

✅ 151. 反转字符串中的单词

image-20260928190002660

image-20260928190002661

题意分析

将字符串中的单词按相反顺序排列，但每个单词内部的字符顺序保持不变。单词是连续的非空格字符，题目中的字符只有英文字母、数字和普通空格，并保证至少包含一个单词。

原字符串可能有前导空格、尾随空格，以及单词之间的多个空格。结果必须去掉首尾空格，并且相邻单词之间恰好保留一个空格，所以不能简单反转整串字符或原样保留分隔符。

题目的常数额外空间进阶以可变字符串为前提。本篇使用的 Java String 和 Go string 都不可变，下面用输出缓冲区构造新字符串，空间复杂度为 $O(n)$。

解法：从右向左提取单词

核心思路

[!blue]

原来的最后一个单词应最先输出，因此从右向左扫描，就能直接按照目标顺序找到各个单词。反向的是寻找单词的顺序，找到一个单词后仍按它在原字符串中的从左到右顺序复制，这样单词内部不会被反转。

用 i 指向尚未处理部分的最右侧。每轮先跳过连续空格；如果此时 i < 0，说明已经没有单词，立即结束。否则用 end = i 保存当前单词的右端点，再继续左移 i，直到遇到空格或越过开头。

此时 i 停在单词左侧，单词实际范围是闭区间 [i + 1, end]。Java 追加子串和 Go 切片都使用右端不包含的范围，因此应读取 [i + 1, end + 1)。当前单词已经完整复制后，下一轮从它左侧继续扫描，不会漏掉或重复读取单词。

不复制原来的空格，而是在已经输出过单词时，先追加一个空格，再追加当前单词。第一个单词前不加空格，最后一个单词后也不主动加空格；任意两个单词之间只在追加后者时加入一个空格，就同时满足了去除首尾空格和压缩连续空格的要求。

指针只向左移动，输出缓冲区只在末尾追加。每个字符被扫描和复制的次数都有固定上界，因此无需拆分出全部单词，也无需对结果再次反转。

解题步骤

  1. 创建输出缓冲区，将 i 放在字符串最后一个字符处。
  2. 向左跳过空格；若 i < 0，结束扫描。
  3. 保存 end = i，继续向左越过本单词的全部非空格字符。
  4. 如果结果非空，先补一个分隔空格，再追加原字符串的 [i + 1, end + 1)。
  5. 重复上述过程，最后把缓冲区转为字符串返回。

代码实现

class Solution {
    public String reverseWords(String s) {
        StringBuilder ans = new StringBuilder();
        int i = s.length() - 1;

        while (i >= 0) {
            while (i >= 0 && s.charAt(i) == ' ') {
                i--;
            }

            // 跳完空格可能已经越过开头，不能继续读取单词。
            if (i < 0) {
                break;
            }

            int end = i;

            while (i >= 0 && s.charAt(i) != ' ') {
                i--;
            }

            // 仅在已经输出过单词时补一个分隔空格，避免首尾多余空格。
            if (ans.length() > 0) {
                ans.append(' ');
            }

            // 扫描停在单词之前，截取区间需要同时包含两端字符。
            ans.append(s, i + 1, end + 1);
        }

        return ans.toString();
    }
}

func reverseWords(s string) string {
    ans := make([]byte, 0, len(s))

    for i := len(s) - 1; i >= 0; {
        for i >= 0 && s[i] == ' ' {
            i--
        }
        // 跳完空格可能已经越过开头，不能继续读取单词。
        if i < 0 {
            break
        }

        end := i
        for i >= 0 && s[i] != ' ' {
            i--
        }

        // 仅在已经输出过单词时补一个分隔空格，避免首尾多余空格。
        if len(ans) > 0 {
            ans = append(ans, ' ')
        }
        // 扫描停在单词之前，截取区间需要同时包含两端字符。
        ans = append(ans, s[i+1:end+1]...)
    }
    return string(ans)
}

复杂度分析

  • 时间复杂度：$O(n)$，指针只从右向左扫描一次，每个非空格字符只追加一次，最终转换字符串也为线性时间。
  • 空间复杂度：$O(n)$，用于输出缓冲区和返回字符串。

关键点总结

[!green]

  • 反向扫描可直接得到反转后的单词顺序，无需额外翻转。
  • 每轮先跳空格，再提取单词，并在两个阶段都检查边界。
  • 空格由结果主动添加，保证单词之间恰好一个空格。
  • 若输入本身是可修改的字符数组，可先原地压缩空格，再反转全部有效字符，最后逐个反转单词：第一次改变单词顺序，第二次恢复单词内部顺序，额外只需常数个指针。把不可变字符串复制成数组仍会占用线性空间。

易错点总结

[!yellow]

  • 跳过空格后未检查指针是否越界，会在前导空格处访问非法下标。
  • 单词左端点应为 i + 1，右端点截取时应包含 end。
  • 每个单词后都追加空格，会留下尾随空格。
  • Java 使用字符串 += 反复拼接，最坏会退化为 $O(n^2)$。

相似题目

题目 难度 关联与区别
186. 反转字符串中的单词 II 中等 单词顺序翻转目标相同，原题以可修改字符数组输入，要求原地完成。
58. 最后一个单词的长度 简单 同样需要先处理空格并定位单词边界，原题只关心最后一个词的长度。
557. 反转字符串中的单词 III 简单 反转单词系列。I 改变单词顺序并保留词内顺序，III 保留词序并反转词内字符，均需识别单词边界。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/82558693
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！