[LeetCode 解題紀錄] 443. String Compression

443. String Compression

https://leetcode.com/problems/string-compression/

Problem:

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

• If the group’s length is 1, append the character to s.
• Otherwise, append the character followed by the group’s length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.

Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

Constraints:

• 1 <= chars.length <= 2000
• chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

題意

建立一個方法，實作特定的演算法來壓縮一個字元陣列 chars ，字元陣列中會是連續的數個不同字元，例如：[“a”,”a”,”b”,”b”,”c”,”c”,”c”]

演算法如下：

• 如果某一個字元只出現一次，則不需要加入長度
• 如果某一個字元出現不只一次，則需要再下一個位置加上出現次數，ex: [“a”,”a”] -> [“a”, “2”]
• 如果超過 10 ，會被拆分成多個字符存儲在 chars 中。ex: [“a”, “1”, “2”]
• 壓縮後的字串 s 不需要單獨返回，而是存儲在輸入的陣列 chars 中。
• 修改輸入後，返回新陣列的長度。

問題解析：

這題有幾個重點要注意，一個是題目要求要直接修改本來的陣列，但是最後只需要回傳修改完後的長度，意思就是其實只關注前面被壓縮的結果，後面本來的字元不需要特別去從陣列裡面刪除。另一個要注意的就是回傳的數字必須是字串的形式，超過位數必須拆開表示。

解法

Two Pointers

回想剛剛有幾個重點，直接修改本來的陣列、只需要回傳修改完後的長度，想法會是在每一個字元的時候，都會先檢查這個字元往後會出現幾次，然後對下一個位置做數量的插入，因此我們需要兩個指針來記錄「目前讀取的位置」與「要寫入的位置」。

Sliding Window / Two Pointers 概念複習：

演算法筆記系列 — Two Pointer 與Sliding Window

• 使用兩個指針：writeIndex 用於指向應該寫入字元的位置，readIndex 用於讀取字元。
• 遍歷 chars 數組，對每個字元進行計數，計數完畢後將字元和計數結果寫入 chars。
• 最後返回新數組的長度 writeIndex。

var compress = function(chars) {
    let writeIndex = 0;
    let readIndex = 0;
    
    while (readIndex < chars.length) {
        let char = chars[readIndex];
        let count = 0;
        
        // 計數連續重複的字元
        while (readIndex < chars.length && chars[readIndex] === char) {
            readIndex++;
            count++;
        }
        
        // 寫入字元
        chars[writeIndex] = char;
        writeIndex++;
        
        // 如果字元數大於1，寫入數字(必須轉成字串形式)
        if (count > 1) {
            // 處理進位問題
            for (let digit of String(count)) {
                chars[writeIndex] = digit;
                writeIndex++;
            }
        }
    }
    
    // 返回新數組的長度
    return writeIndex;
};

• 時間複雜度：O(N)
• 空間複雜度：O(1)

更多演算法與資料結構文章：

基礎演算法與資料結構學習筆記