LeetCode如何翻转字符串里的单词

# LeetCode如何翻转字符串里的单词

## 问题描述

LeetCode第151题"翻转字符串里的单词"要求我们实现一个算法，将给定字符串中的单词顺序进行翻转，同时去除多余的空格。具体要求如下：

- 输入字符串可能包含前导空格、尾随空格和单词间的多个空格
- 返回的字符串应当单词顺序翻转，且单词间用单个空格分隔
- 不能使用任何内置的字符串处理函数（如split、reverse等）

示例：

输入: “ hello world ” 输出: “world hello”

## 解题思路分析

### 方法一：双指针法（最优解）

**核心思想**：先整体翻转字符串，再逐个翻转单词，最后处理空格

1. **去除多余空格**：使用快慢指针法去除字符串中多余的空格
2. **整体翻转**：将整个字符串进行翻转
3. **单词翻转**：识别每个单词的边界，对每个单词进行局部翻转
4. **调整格式**：确保单词间只有一个空格

**时间复杂度**：O(n)  
**空间复杂度**：O(1)（对于C++等可修改字符串的语言）

### 方法二：使用栈

**核心思想**：利用栈的先进后出特性实现翻转

1. 遍历字符串，提取单词并压入栈中
2. 依次弹出栈中单词组成新字符串
3. 处理空格问题

**时间复杂度**：O(n)  
**空间复杂度**：O(n)

### 方法三：分割+反转（不符合题目要求但实际常用）

虽然题目限制使用内置函数，但在实际开发中可以：
1. 使用split分割单词
2. 反转单词列表
3. 用join连接

## 代码实现（以方法一为例）

### Python实现
```python
def reverseWords(s: str) -> str:
    # 去除多余空格
    def trim_spaces(s):
        left, right = 0, len(s) - 1
        # 去掉首尾空格
        while left <= right and s[left] == ' ':
            left += 1
        while left <= right and s[right] == ' ':
            right -= 1
        
        # 去掉中间多余空格
        output = []
        while left <= right:
            if s[left] != ' ':
                output.append(s[left])
            elif output[-1] != ' ':
                output.append(s[left])
            left += 1
        return output
    
    # 反转字符数组
    def reverse(l, left, right):
        while left < right:
            l[left], l[right] = l[right], l[left]
            left += 1
            right -= 1
    
    # 反转每个单词
    def reverse_each_word(l):
        n = len(l)
        start = end = 0
        while start < n:
            # 找到单词末尾
            while end < n and l[end] != ' ':
                end += 1
            # 反转单词
            reverse(l, start, end - 1)
            # 更新指针
            start = end + 1
            end += 1
    
    # 主流程
    l = trim_spaces(s)
    reverse(l, 0, len(l) - 1)
    reverse_each_word(l)
    return ''.join(l)

Java实现

class Solution {
    public String reverseWords(String s) {
        // 去除空格
        StringBuilder sb = trimSpaces(s);
        // 翻转字符串
        reverse(sb, 0, sb.length() - 1);
        // 翻转每个单词
        reverseEachWord(sb);
        return sb.toString();
    }
    
    public StringBuilder trimSpaces(String s) {
        int left = 0, right = s.length() - 1;
        while (left <= right && s.charAt(left) == ' ') left++;
        while (left <= right && s.charAt(right) == ' ') right--;
        
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ') {
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            left++;
        }
        return sb;
    }
    
    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }
    
    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0, end = 0;
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') end++;
            reverse(sb, start, end - 1);
            start = end + 1;
            end++;
        }
    }
}

边界条件与测试用例

常见测试用例

1. 常规情况：
   • 输入：”the sky is blue”
   • 输出：”blue is sky the”
2. 包含多个空格：
   • 输入：” hello world “
   • 输出：”world hello”
3. 前后有空格：
   • 输入：” Bob Loves Alice “
   • 输出：”Alice Loves Bob”
4. 单字单词：
   • 输入：”a good example”
   • 输出：”example good a”
5. 全空格：
   • 输入：” “
   • 输出：””

特殊测试用例

1. 空字符串：
   • 输入：””
   • 输出：””
2. 连续多个空格：
   • 输入：”a b c d”
   • 输出：”d c b a”
3. 单个单词：
   • 输入:“hello”
   • 输出:“hello”

算法优化与变种

优化点

1. 字符串拼接优化：在Java中使用StringBuilder而非String直接拼接
2. 原地修改：对于C++等语言可以直接修改原字符串
3. 双指针优化：在去除空格时可以使用更高效的双指针法

相关问题变种

1. 翻转字符串II（LeetCode 541）：每隔2k字符翻转前k个
2. 翻转字符串中的单词III（LeetCode 557）：翻转每个单词但保持顺序
3. 旋转字符串（LeetCode 796）：检查是否可以通过旋转得到

常见错误与注意事项

1. 空格处理不当：
   • 忘记处理前导/尾随空格
   • 单词间保留多个空格
2. 边界条件遗漏：
   • 空字符串情况
   • 全空格字符串
3. 原地修改问题：
   • 在某些语言中字符串不可变，需要转换为数组
4. 指针越界：
   • 在双指针法中未正确处理指针移动

总结

翻转字符串中的单词是一个考察综合字符串处理能力的问题，涉及： 1. 字符串基本操作 2. 双指针技巧 3. 翻转操作实现 4. 边界条件处理

掌握这类问题有助于提升对字符串处理的整体理解，并为更复杂的算法问题打下基础。建议在理解基础解法后，尝试自己实现并考虑各种优化可能性。 “`