String Compression

題目描述

給定字元陣列 chars，原地壓縮。連續相同字元替換為「字元+計數」（計數為 1 時省略）。回傳壓縮後陣列的長度。

輸入：chars = ["a","a","b","b","c","c","c"]
輸出：6（陣列變為 ["a","2","b","2","c","3"]）

輸入：chars = ["a"]
輸出：1

輸入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
輸出：4（陣列變為 ["a","b","1","2"]）

解題思路

初始化

write = 0（下一個寫入位置），read = 0（當前讀取位置）

計算連續字元

內層 while 迴圈：從 read 開始，當 chars[read] 等於當前字元時 read++ 和 count++

寫入字元

把當前字元寫入 chars[write]，write 前進一格

寫入計數

若 count > 1，把 count 轉為字串（如 12 → "1","2"），逐字元寫入 chars[write++]

繼續

read 已指向下一組不同字元的起點，回到步驟 2 重複直到 read 到底

程式碼

C#

csharp

public class Solution {
    public int Compress(char[] chars) {
        int write = 0, read = 0;
        while (read < chars.Length) {
            char current = chars[read];
            int count = 0;
            // 計算連續相同字元數
            while (read < chars.Length && chars[read] == current) {
                read++;
                count++;
            }
            // 寫入字元
            chars[write++] = current;
            // 寫入計數（大於 1 時）
            if (count > 1) {
                foreach (char c in count.ToString())
                    chars[write++] = c;
            }
        }
        return write;
    }
}

TypeScript

typescript

function compress(chars: string[]): number {
    let write = 0, read = 0;
    while (read < chars.length) {
        const current = chars[read];
        let count = 0;
        while (read < chars.length && chars[read] === current) {
            read++;
            count++;
        }
        chars[write++] = current;
        if (count > 1) {
            for (const c of count.toString()) {
                chars[write++] = c;
            }
        }
    }
    return write;
}

Python

python

def compress(chars: list[str]) -> int:
    write = read = 0
    while read < len(chars):
        current = chars[read]
        count = 0
        while read < len(chars) and chars[read] == current:
            read += 1
            count += 1
        chars[write] = current
        write += 1
        if count > 1:
            for c in str(count):
                chars[write] = c
                write += 1
    return write

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |

read 指針從頭到尾掃描一遍 O(n)，write 指針最多寫 n 個字元。原地修改不需額外陣列，只用 write、read、count 等常數變數，空間 O(1)。

邊界情況

每個字元都不重複：例如 ["a","b","c"]，每組 count=1 不寫數字，壓縮後長度不變
只有一個字元：例如 ["a"]，回傳長度 1
連續超過 9 個：例如 12 個 b，需要寫入 "b","1","2" 三個字元，count.toString() 產生多位數字

圖解

[a,a,b,b,c,c,c]

read 掃描 aa→

寫入 a,2

read 掃描 bb→

寫入 b,2

read 掃描 ccc→

寫入 c,3

完成→

[a,2,b,2,c,3] len=6

圖表展示三組壓縮：read 先掃描兩個 a（count=2），write 寫入 a,2；接著掃描兩個 b，寫入 b,2；最後三個 c，寫入 c,3。原陣列長度 7 壓縮為 6。

進階觀點

💡面試追問

計數超過 9 怎麼處理？ 把 count 轉為字串後逐字元寫入。例如 count=12 轉為 "12"，寫入 '1' 和 '2' 兩個字元。C# 用 count.ToString()，Python 用 str(count)。
為什麼寫入指針不會超過讀取指針？ 一個字元出現 n 次，壓縮後佔 1+len(str(n)) 格。當 n=1 時佔 1 格（省略計數），n ≥ 2 時 1+digits(n) ≤ n（例如 n=2 佔 2 格，n=10 佔 3 格）。所以壓縮後長度永遠 ≤ 原始長度。
Run-Length Encoding 的應用？ BMP 影像格式、傳真機資料傳輸、遊戲地圖壓縮都用 RLE。它對連續重複資料效果極佳，但對隨機資料可能反而膨脹。

理解測驗

🤔 為什麼 write 指針永遠不會超過 read 指針？

🤔 chars = ["a","b","c"] 壓縮後結果是什麼？