劍指 Offer 面試題 4：字符串替換空格——O(n) 原地演算法與 StringBuffer 實現

經典字符串題：將字符串中每個空格替換為 %20。本文講解兩種 O(n) 解法——陣列從後向前原地替換（面試首選）與 StringBuffer 索引查找（工程實用），附完整 Java 代碼、邊界測試與複雜度分析。

題目描述

輸入："We are happy."
輸出："We%20are%20happy."

輸入：" We are happy. "
輸出："%20We%20are%20happy.%20"

核心觀察

• 空格 → %20 長度 +2，需擴容。
• Java String 不可變，需轉 char[] 或用 StringBuffer 操作。
• 從前向後替換需反覆移動後續字符 O(n²)；從後向前 單次掃描 O(n)。

解法一：字符陣列從後向前原地替換（最優）

演算法步驟

1. 統計空格數 spaceCount，計算新長度 newLen = oldLen + 2 * spaceCount。
2. 分配新陣列 char[] newArr = new char[newLen]。
3. 雙指針：i = oldLen - 1 (舊末尾)、j = newLen - 1 (新末尾)。
4. 倒序掃描：
   - old[i] != ' ' → newArr[j--] = old[i--]
   - old[i] == ' ' → newArr[j]='0'; newArr[j-1]='2'; newArr[j-2]='%'; j-=3; i--
5. 返回 new String(newArr)。

完整代碼

public static String replaceSpace(char[] str) {
    if (str == null) return null;
    int oldLen = str.length;
    int spaceCount = 0;
    for (char c : str) if (c == ' ') spaceCount++;

    int newLen = oldLen + 2 * spaceCount;
    char[] newArr = new char[newLen];

    int i = oldLen - 1, j = newLen - 1;
    while (i >= 0) {
        if (str[i] == ' ') {
            newArr[j--] = '0';
            newArr[j--] = '2';
            newArr[j--] = '%';
        } else {
            newArr[j--] = str[i];
        }
        i--;
    }
    return new String(newArr);
}

複雜度

• 時間：O(n) 兩次線性掃描
• 空間：O(n) 新陣列（Java 無法原地擴容 char[]）

解法二：StringBuffer + indexOf/subSequence（工程友好）

思路

• 利用 StringBuffer.indexOf(" ", fromIndex) 定位下一個空格。
• subSequence(from, index) 取非空格段落，append 到結果緩衝區，再 append("%20")。
• 循環直到 indexOf 返回 -1，最後追加剩餘尾部。

完整代碼

public static String replaceSpace(StringBuffer sb) {
    if (sb == null) return null;
    StringBuffer result = new StringBuffer();
    int from = 0, index = 0;
    while ((index = sb.indexOf(" ", from)) >= 0) {
        result.append(sb.subSequence(from, index)).append("%20");
        from = index + 1;
    }
    result.append(sb.substring(from)); // 剩餘尾部
    return result.toString();
}

複雜度

• 時間：O(n) — indexOf 內部優化，整體線性
• 空間：O(n) 結果緩衝區
• 優點：代碼簡潔、可讀性強、自動處理擴容、線程安全

邊界測試用例

面試延伸：若在字符陣列中原地替換（預留足夠空間）

C/C++ 常見變體：假設 char str[100] 末尾有足夠空間，無需額外陣列 真正 O(1) 空間：

// C 風格偽碼
int oldLen = strlen(str);
int spaceCount = count_spaces(str);
int newLen = oldLen + 2 * spaceCount;
str[newLen] = '\0';
for (int i = oldLen - 1, j = newLen - 1; i >= 0; i--) {
    if (str[i] == ' ') {
        str[j--] = '0'; str[j--] = '2'; str[j--] = '%';
    } else {
        str[j--] = str[i];
    }
}

Java char[] 長度不可變，無法直接應用，但理解此思維有助於解決「合併兩個有序陣列」「移除元素」等原地修改題。

總結

替換空格考察「從後向前掃描避免重複移動」的陣列技巧與 StringBuffer 實戰能力。面試建議：首寫陣列雙指針版展示演算法功力，再補 StringBuffer 版說明工程落地；邊界情況（null、空串、首尾空格）主動測試，體現嚴謹風格。