面试题 01.06. 字符串压缩
Table of Contents
一、中文版
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
示例1:
输入："aabcccccaaa"
输出："a2b1c5a3"
示例2:
输入："abbccd"
输出："abbccd"
解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
提示：
字符串长度在[0, 50000]范围内。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/compress-string-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、英文版
Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z). Example 1: Input: "aabcccccaaa" Output: "a2b1c5a3" Example 2: Input: "abbccd" Output: "abbccd" Explanation: The compressed string is "a1b2c2d1", which is longer than the original string. Note: 0 <= S.length <= 50000 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/compress-string-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
三、My answer
class Solution: def compressString(self, S: str) -> str: if not S: return "" s_list = list(S) res = '' i = 1 base = 1 while i < len(s_list): if s_list[i] == s_list[i-1]: base += 1 else: res = res + str(s_list[i-1]) + str(base) base = 1 i += 1 res = res + str(s_list[len(s_list)-1]) + str(base) if len(res) >= len(S): return S return res
四、解题报告
上面代码中，base 用来统计每个字母出现的个数，当发现当前字母与前一个字母不一样时，base 重置为0。
此外，最后一个字母需要特殊判别，也就是 while 循环结束后还要再处理一下 res 的原因。
下面官方题解更简洁清晰，记录学习：
class Solution: def compressString(self, S: str) -> str: if not S: return "" ch = S[0] ans = '' cnt = 0 for c in S: if c == ch: cnt += 1 else: ans += ch + str(cnt) ch = c cnt = 1 ans += ch + str(cnt) return ans if len(ans) < len(S) else S
