字串壓縮 String Compression_Leetcode 精選75題

Waldemar null on Unsplash

題目敘述

題目會給我們一個輸入陣列chars，要求我們把同樣的字元作分類並且依照長度做編碼壓縮。壓縮時，必須在陣列做in-place原地更新，最後回傳壓縮之後的字串長度。

壓縮規則:

同樣的字元一群，首項放字元，假如這群的長度只有1，那這群的壓縮就完成了。假如假如這群的長度大於1，那麼後面緊接著以字元的形式，放入這群的長度。

例如輸入['a','a','a'] 壓縮完變成['a','3'] 長度為2

例如輸入['a','b'] 壓縮完變成['a','b'] 長度為2

題目的原文敘述

測試範例

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".

約束條件

• 1 <= chars.length <= 2000

輸入陣列chars的長度介於1~2000之間

• chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

chars內不包含的只會是大寫英文字母、小寫英文字母、數字、或者符號。

演算法

這邊可以使用經典的雙指針來解。

宣告兩個變數，slow和fast，初始化為零，代表起頭位置。

從左邊開始向右掃描每一群，slow負責壓縮後對應要填的位置，fast負責去量測同一群字元的長度，並且紀錄在計數器count裡面。

程式碼

class Solution:
    def compress(self, chars: List[str]) -> int:
        slow, fast = 0, 0
        n = len(chars)

        while fast < n:
            
            # Update leading character
            chars[slow] = chars[fast]
            count = 1
			
			       # Measure the length of cluster with same character
            while (fast + 1) < n and chars[fast] == chars[fast+1]:
                fast += 1
                count += 1
			
			       # Write length of current cluster
            if count > 1:
                for c in str(count):
                    chars[slow+1] = c
                    slow += 1
            
            # Moving to right hand side
            fast += 1
            slow += 1
        
        return slow