压缩字符串(一)

压缩字符串(一)_牛客题霸_牛客网

问题简述

利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2bc5a3。
1.如果只有一个字符，1不用写
2.字符串中只包含大小写英文字母（a至z）。

思路：滑动窗口

• 定义窗口 [l, r]（闭区间）；

• 当 s[l] == s[r] 时，移动 r；否则，添加 s[l] 和 r - l 到结果，并将 l 移动到 r 位置，开启下一个窗口；

• 注意最后一个窗口，r 的循环区间应该是 [0, N]，而不是 [0, N-1]，所以在判断 s[l] == s[r] 时要注意边界；

Python

class Solution:
    def compressString(self , s ):
        if not s: return ''
        
        N = len(s)
        ret = []
        
        l, r = 0, 0
        while r <= N:  # r 需要遍历到最后一个字符的下一个位置
            # 当不满足条件时，直接移动 l 到 r，不需要 while 判断
            if r == N or s[l] != s[r]:  # 注意判断顺序
                ret.append(s[l])
                if r > l + 1:
                    ret.append(str(r - l))
                l = r
            r += 1
            
        return ''.join(ret)