LeetCode 151: 反转字符串中的单词 - 深入解析与实现

问题描述

题目链接: 151. 反转字符串中的单词

题目要求我们反转一个给定字符串 s 中单词的顺序。

• 单词：由非空格字符组成的序列。
• 分隔符：单词之间由至少一个空格隔开。
• 输出要求：返回一个新字符串，其中单词顺序颠倒，且单词之间仅由单个空格连接。此外，结果字符串不应包含任何前导或尾随空格。

示例:

• 输入: s = "the sky is blue"

• 输出: "blue is sky the"

• 输入: s = " hello world "

• 输出: "world hello" (注意移除了多余的空格)

• 输入: s = "a good example"

• 输出: "example good a" (单词间多个空格变单个)

思路分析

初看此题，最直观的想法可能是将字符串按空格分割成单词数组，然后反转数组，最后再用单个空格拼接起来。这在很多语言中都可以通过内置库函数轻松实现。

但是毕竟是中等题，调库解决不太尊重，还是手动实现吧。

最直观的思路就是：直接遍历原始字符串，逐个识别出单词，并将其“头插法”式地构建到新的字符串中。这样，第一个被识别的单词自然就跑到了新字符串的末尾，而最后一个被识别的单词则会出现在新字符串的开头，完美实现了单词顺序的反转。

这种方法的核心优势在于：

1. 一次遍历：我们只需要从头到尾遍历一次原始字符串。
2. 空间效率：我们只需要一个额外的数据结构（如 StringBuilder）来构建结果，避免了存储中间单词数组的开销。
3. 空格处理：在识别单词和构建新字符串的过程中，可以非常自然地处理掉多余的空格。

Java 代码实现与详解

下面是我们采用上述思路实现的 Java 代码。

public String reverseWords(String s) {
    int len = s.length();
    StringBuilder s2 = new StringBuilder();
    int i=0;
    while (i<len) {
        // 找到单词序列，首个非空，直接下个为空或结束
        int w_len=0;//当前单词长度
        while (i<len && s.charAt(i)==' ') i++;
        if(!s2.isEmpty() && i<len )
            s2.insert(0,' ');
        while (i<len && s.charAt(i)!=' '){
            s2.insert(w_len, s.charAt(i));
            i++;
            w_len++;
        }
    }
    return s2.toString();
}

复杂度分析

• 时间复杂度: O(N)，其中 N 是字符串 s 的长度。我们只对字符串进行了一次完整的遍历。虽然 StringBuilder.insert(0, ...) 在理论上可能涉及数组移动，也是 O(k) 的操作（k为当前builder长度），但由于每个字符只被处理有限次，总的来看，整体时间复杂度依然是线性的。
• 空间复杂度: O(N)，我们需要一个 StringBuilder 来存储结果，最坏情况下，它会存储整个字符串的内容。