題目

難度：★★☆☆☆
類型：字符串

給定一組字符，使用原地算法將其壓縮。

壓縮后的長度必須始終小于或等于原數(shù)組長度。

數(shù)組的每個元素應該是長度為1 的字符（不是 int 整數(shù)類型）。

在完成原地修改輸入數(shù)組后，返回數(shù)組的新長度。

進階：
你能否僅使用O(1) 空間解決問題？

注意：
所有字符都有一個ASCII值在[35, 126]區(qū)間內(nèi)。
1 <= len(chars) <= 1000。

示例

示例 1：
輸入：
["a","a","b","b","c","c","c"]
輸出：
返回6，輸入數(shù)組的前6個字符應該是：["a","2","b","2","c","3"]
說明：
"aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。

示例 2：
輸入：
["a"]
輸出：
返回1，輸入數(shù)組的前1個字符應該是：["a"]
說明：
沒有任何字符串被替代。

示例 3：
輸入：
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
輸出：
返回4，輸入數(shù)組的前4個字符應該是：["a","b","1","2"]。
說明：
由于字符"a"不重復，所以不會被壓縮。"bbbbbbbbbbbb"被“b12”替代。
注意每個數(shù)字在數(shù)組中都有它自己的位置。

解答

參考了一個大佬的評論。。。

class Solution:
    def compress(self, chars: List[str]) -> int:
        from itertools import groupby
        i = 0

        def w(s):
            nonlocal i
            for c in s:
                chars[i] = c
                i += 1
                
        for c, g in groupby(chars):
            w(c)
            g = len(tuple(g))
            if g > 1:
                w(str(g))
                
        return i

如有疑問或建議，歡迎評論區(qū)留言~