算法 - 反转字符串中的单词

Posted on

1. 题目

给你一个字符串 s，反转其中单词的顺序并返回。单词是由非空格字符组成的最大子串，单词间由一个或多个空格分隔。返回的字符串中单词之间只用单个空格分隔，且不含前导或尾随空格。

示例:

1
2
3
4
5
6
7
8
输入: "the sky is blue"
输出: "blue is sky the"

输入: "  hello   world  "
输出: "world hello"

输入: "a good   example"
输出: "example good a"

2. 解题思路

要求处理多余空格，思路分两种：

2.1 内建 API 版（快速）

  1. trim() 去首尾空格。
  2. split(/\s+/) 按「一个或多个空白」切成单词数组（首尾已 trim，不会有空串）。
  3. reverse() 反转数组。
  4. join(" ") 用单空格连接。

优点：一行思路、代码短、面试先写它保底。缺点：依赖高级 API，没有体现手写能力。

2.2 双指针手写版（加分）

从右向左扫描：跳过空格 → 定位一个单词的右端与左端 → 截取单词追加到结果，单词间补一个空格。天然实现「逆序 + 单空格」。

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)（存放结果；若原地翻转则为 O(1)）。

若题目要求原地（C 风格字符数组），经典三步：整体反转 → 逐个单词再反转 → 压缩多余空格，做到 O(1) 额外空间。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 2.1 API 版
function reverseWords(s: string): string {
    return s.trim().split(/\s+/).reverse().join(" ");
}

// 2.2 双指针手写版（从右往左）
function reverseWordsTwoPointer(s: string): string {
    const res: string[] = [];
    let i = s.length - 1;

    while (i >= 0) {
        // 跳过空格
        if (s[i] === " ") {
            i--;
            continue;
        }
        // 定位单词左端
        let j = i;
        while (j >= 0 && s[j] !== " ") j--;
        // j+1 .. i 是一个单词
        res.push(s.slice(j + 1, i + 1));
        i = j; // 继续向左
    }

    return res.join(" ");
}

console.log(reverseWords("  hello   world  ")); // "world hello"
console.log(reverseWordsTwoPointer("a good   example")); // "example good a"

4. 面试延伸

  • 正则 /\s+/ 的坑：若不用 trim 直接 split，首尾会产生空字符串元素，需 .filter(Boolean)。
  • 原地版（186 题，字符数组）：整串 reverse + 每词 reverse + 移除多余空格，O(1) 空间，最能区分候选人。
  • 关联：左旋转字符串（剑指 Offer 58-II） = 反转整体 + 反转各段，考察同一套「翻转」思想。
  • JS 里 String.prototype.reverse 不存在，别忘了 split("") 或数组中转，容易口误。
  • 能顺手讨论「多个空格 / 首尾空格 / 空串」这些边界，是字符串题的基本素养。

难度：中等 | LeetCode 151 题 | 字符串与双指针