该题解通过遍历字符串S,并计算每个字符连续出现的次数来构造压缩后的字符串。遍历过程中,用ch_prev记录前一个字符,用count记录该字符的连续出现次数。为了简化末尾字符的处理,给字符串S额外添加了一个不同的字符'@'作为结束标记。这样,当遇到新字符或结束字符'@'时,将前一个字符及其计数追加到结果字符串ret中。最后比较压缩后字符串的长度与原字符串的长度,如果压缩后没有变短,则返回原字符串。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def compressString(self, S: str) -> str:
if S == '':
return S
else:
ch_prev = S[0] # 初始化前一个字符
count = 0 # 初始化计数器
ret = '' # 初始化结果字符串
T = S + '@' # 在原字符串末尾添加一个不同的字符
for ch in T:
if ch == ch_prev:
count = count + 1 # 相同字符计数加一
else:
ret = ret + ch_prev # 追加前一个字符
ret = ret + str(count) # 追加字符计数
count = 1 # 重置计数器
ch_prev = ch # 更新前一个字符
if len(S) > len(ret):
return ret # 压缩有效,返回压缩字符串
else:
return S # 压缩无效,返回原字符串