您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

LeetCode 151 翻轉字串中的單詞：O(1) 空間複雜度最優解法詳解

編輯：Java 綜合教學

LeetCode 151 翻轉字串中的單詞：O(1) 空間複雜度最優解法詳解

LeetCode 151 題要求：給定一個輸入字串，按單詞順序反轉。例如 "the sky is blue" → "blue is sky the"。本文從暴力解法進階到 O(1) 額外空間的原地演算法，詳細分析字串處理的關鍵技巧與陷阱。

題目需求與約束

單詞由非空格字符組成
輸入字串可能包含前導、尾隨或多個連續空格
輸出單詞間僅保留單個空格，無前尾空格
進階挑戰：C 語言嘗試 O(1) 空間複雜度原地解決

解法演進分析

❌ 方案一：字串拼接（不可取）

// 思路：分割單詞 → 反轉順序 → 拼接
// 缺點：每次拼接創建新 String 物件，O(n²) 時間，記憶體碎片嚴重
private String ReWords(String s) {
    String result = " ";
    for (int i = 0; i < s.length(); i++) {
        int j = i;
        while (j < s.length() && Character.isLetter(s.charAt(j))) j++;
        String word = s.substring(i, j);
        result = word + result; // 每次創建新字串！
        i = j;
    }
    return result.trim();
}

✅ 方案二：StringBuilder 線性構建（標準解）

public String reverseWords(String s) {
    StringBuilder reversed = new StringBuilder();
    int j = s.length(); // 單詞結束邊界（不包含）
    
    // 從右向左掃描
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == ' ') {
            j = i; // 更新單詞結束位置
        } 
        // 發現單詞開頭：i==0 或前一字符是空格
        else if (i == 0 || s.charAt(i - 1) == ' ') {
            if (reversed.length() != 0) {
                reversed.append(' '); // 單詞間加空格
            }
            // substring(i, j) 取得 [i, j) 區間單詞
            reversed.append(s.substring(i, j));
        }
    }
    return reversed.toString();
}

關鍵技巧解析

逆向掃描：從字串末尾向前，天然實現單詞順序反轉
雙邊界追蹤：j 記錄單詞結束位置，i 為掃描指標，遇到空格更新 j，遇到單詞開頭提取 s.substring(i, j)
空格處理：僅在 reversed 已有內容時追加空格，避免首尾空格
StringBuilder：可變字串緩衝區，O(1) 擴容攤銷，避免字串拼接創建大量臨時物件

✅ 方案三：Java 原地演算法（字元陣列，O(1) 額外空間）

Java String 不可變，需轉 char[] 操作，最後構建新 String（輸出不計入額外空間）。

public String reverseWords(String s) {
    char[] arr = s.toCharArray();
    int n = arr.length;
    
    // 步驟 1：整體反轉字元陣列
    reverse(arr, 0, n - 1);
    
    // 步驟 2：反轉每個單詞內部字元順序
    int start = 0, end = 0;
    while (start < n) {
        // 跳過空格
        while (start < n && arr[start] == ' ') start++;
        if (start >= n) break;
        end = start;
        while (end < n && arr[end] != ' ') end++;
        // 反轉 [start, end-1]
        reverse(arr, start, end - 1);
        start = end;
    }
    
    // 步驟 3：清理多餘空格（雙指針原地壓縮）
    int write = 0, read = 0;
    while (read < n) {
        // 跳過前導/連續空格
        while (read < n && arr[read] == ' ') read++;
        if (read >= n) break;
        // 複製單詞
        if (write > 0) arr[write++] = ' '; // 單詞間加單空格
        while (read < n && arr[read] != ' ') {
            arr[write++] = arr[read++];
        }
    }
    
    return new String(arr, 0, write); // 截取有效部分
}

private void reverse(char[] arr, int l, int r) {
    while (l < r) {
        char tmp = arr[l];
        arr[l++] = arr[r];
        arr[r--] = tmp;
    }
}

複雜度分析

解法	時間複雜度	空間複雜度	備註
字串拼接	O(n²)	O(n²)	大量臨時物件，GC 壓力大
StringBuilder	O(n)	O(n)	標準解，生產環境推薦
原地 char[]	O(n)	O(1) 額外	面試進階要求，展示演算法功力

邊界情況測試

// 測試用例
reverseWords("the sky is blue")        // "blue is sky the"
reverseWords("  hello world  ")        // "world hello"
reverseWords("a good   example")       // "example good a"
reverseWords("")                       // ""
reverseWords("   ")                    // ""
reverseWords("a")                      // "a"
reverseWords("  a  b  ")               // "b a"