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. 邊界條件處理

掌握這類問題有助于提升對字符串處理的整體理解，并為更復雜的算法問題打下基礎。建議在理解基礎解法后，嘗試自己實現并考慮各種優化可能性。 “`