劍指 Offer 面試題 02：替換空格——原地替換 O(N) 時間 O(1) 空間解法

劍指 Offer 面試題 02：替換空格——原地替換 O(N) 時間 O(1) 空間解法

題目： 實現一個函數，將字串中的空格替換為「%20」。例如輸入 "We Are Happy"，輸出 "We%20Are%20Happy"。

核心挑戰

替換後字串長度增加（每個空格 +2 字元）。若從前往後替換，需不斷移動後續字元，時間複雜度退化為 O(N²)。

最優解：從後往前雙指針原地替換，時間 O(N)、額外空間 O(1)（假設字串緩衝區足夠大）。

演算法步驟

1. 先掃描一次統計空格數 spaceCount
2. 計算新長度：newLength = oldLength + spaceCount * 2
3. 設置雙指針：i = oldLength - 1（舊尾）、j = newLength - 1（新尾）
4. 從後往前遍歷：
   • 若 str[i] != ' '：str[j--] = str[i--]
   • 若 str[i] == ' '：str[j--] = '0'; str[j--] = '2'; str[j--] = '%'; i--
5. 完成

Java 實現（使用 StringBuffer 模擬字元陣列）

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int spaceCount = 0;
        // 1. 統計空格數
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') spaceCount++;
        }

        int oldIdx = str.length() - 1;
        int newIdx = str.length() + spaceCount * 2 - 1;
        
        // 擴容 StringBuffer 到新長度
        str.setLength(newIdx + 1);
        
        // 2. 從後往前填充
        for (int i = oldIdx; i >= 0; i--) {
            char c = str.charAt(i);
            if (c != ' ') {
                str.setCharAt(newIdx--, c);
            } else {
                str.setCharAt(newIdx--, '0');
                str.setCharAt(newIdx--, '2');
                str.setCharAt(newIdx--, '%');
            }
        }
        return str.toString();
    }
}

測試結果

輸入: "We Are Happy"
輸出: "We%20Are%20Happy"

複雜度分析

• 時間複雜度：O(N) — 兩次線性掃描
• 空間複雜度：O(1) — 僅使用常數額外變數（StringBuffer 擴容不計入額外空間）

延伸思考

• 若語言不支援可變字元陣列（如 Java String 不可變），需建立新陣列，空間複雜度為 O(N)
• 面試中可討論：為何從後往前？如何處理 Unicode 空格？若是 URL 編碼其他字元如何擴展？

此題考察雙指針技巧與原地修改數組的基本功，是字串操作類面試題的經典入門。