难度: Easy
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
示例1:
输入："aabcccccaaa" 输出："a2b1c5a3"
示例2:
输入："abbccd" 输出："abbccd" 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
提示：
运行时间: 26 ms
内存: 16.1 MB
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
该题解通过遍历字符串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 # 压缩无效，返回原字符串
在字符串'S'末尾添加'@'字符主要是为了简化代码逻辑，确保可以正确处理原字符串中最后一个字符序列的压缩。由于压缩过程需要检测到字符变化时才记录前一个字符的出现次数，如果不添加结束标记，循环结束时需要额外的逻辑来处理最后一组字符。添加一个不常见的字符如'@'作为结束标记，可以在循环中统一处理所有字符的结束，避免了在循环外单独处理最后一组字符的复杂性。
如果原始字符串'S'中已经包含了'@'字符，那么使用'@'作为结束标记将不再有效，因为算法会误认为字符串结束了，从而导致压缩结果错误。在这种情况下，需要选择一个保证不会出现在原字符串中的字符作为结束标记，或者需要改变方法，例如通过检查是否到达字符串的实际末尾来结束循环，而不依赖于特定的结束标记字符。
在循环过程中终止并返回原字符串的做法可能听起来可以提前结束处理，节省时间。但是，由于无法预先知道压缩的结果长度（因为字符序列的长度和分布未知），只有在完全构建完压缩后的字符串后，才能准确知道其长度。因此，必须等到循环完成后，才能进行长度比较，并决定是否返回压缩字符串或原字符串。这样可以保证压缩逻辑的正确性和完整性。