LeetCode 面试题 01.06. 字符串压缩
目录
题目描述
题意分析
输入是一个只含大小写字母的字符串，要把每一段连续相同的字符写成「字符 + 该段长度」的形式，例如
aabcccccaaa变成a2b1c5a3。关键限定有两个：一是压缩的对象是连续段，不是字符在全串中的总出现次数，散落在不同位置的相同字符不能合并；二是压缩完还要比长度，只有压缩串严格更短才返回它，否则原样返回输入。
约束信号：字符集只有字母，不用担心数字与字符混淆；长度上限五万，说明要一次线性扫描完成，并且拼接结果时不能用会产生大量中间对象的写法。
边界包括：空串与长度为 1 的串（压缩后必然不会更短）；全串同一个字符（压缩收益最大）；相邻字符全不相同（压缩后长度翻倍）；某段长度达到两位数甚至五位数；最后一段直到扫描结束才闭合。
解法：连续段计数模拟
核心思路
压缩单位是连续相同字符形成的段，不能用哈希表统计全局频次。例如
aabaa有三段，应得到a2b1a2，而不是a4b1。用左右指针扫描每一段：
left指向段首，right找到第一个不同字符，于是当前字符是S[left]，段长是right - left。写入后令left = right，继续处理下一段。循环不变量是：每轮开始时，
[0, left)已被完整压缩，left正好指向下一段段首；因此每个字符只会被扫描一次。压缩结果只会继续变长，一旦其长度达到原串长度，就可直接返回原串；否则全部处理完后，仍要用“严格更短”判断是否采用压缩结果。
解题步骤
- 初始化
left = 0和结果缓冲区。- 从
left + 1开始移动right，直到越界或字符变化。- 追加
S[left]与段长right - left。- 若当前结果长度已不小于原串，直接返回原串；否则令
left = right。- 所有段处理完后返回压缩串。
以
aabcccccaaa为例，依次识别出aa | b | ccccc | aaa，写成a2b1c5a3，长度 8 小于原串长度 11，因此返回压缩串。对于aabb，写到a2b2时长度等于原串，必须返回aabb。
代码实现
class Solution {
public String compressString(String S) {
int n = S.length();
StringBuilder compressed = new StringBuilder();
for (int left = 0; left < n; ) {
int right = left + 1;
while (right < n && S.charAt(right) == S.charAt(left)) {
right++;
}
compressed.append(S.charAt(left)).append(right - left);
if (compressed.length() >= n) {
return S;
}
left = right;
}
return compressed.toString();
}
}
import "strconv"
func compressString(S string) string {
compressed := make([]byte, 0, len(S))
for left := 0; left < len(S); {
right := left + 1
for right < len(S) && S[right] == S[left] {
right++
}
compressed = append(compressed, S[left])
compressed = strconv.AppendInt(compressed, int64(right-left), 10)
if len(compressed) >= len(S) {
return S
}
left = right
}
return string(compressed)
}
复杂度分析
- 时间复杂度：$O(n)$。左右指针只向前移动，每个字符至多被检查一次。
- 空间复杂度：$O(n)$。最坏情况下结果缓冲区与原串同阶；提前判定不改变渐进复杂度。
关键点总结
- 统计的是连续段，不是字符在整串中的总频次。
[left, right)精确表示当前段，段长直接是right - left，无需单独处理最后一段。- 只有压缩串严格更短时才能返回；等长也返回原串。
- 面试时应说明为何使用可变缓冲区：循环内直接拼接不可变字符串可能退化为 $O(n^2)$。
易错点总结
- 把非相邻的相同字符合并：
aabaa不能写成a4b1。- 漏掉严格比较：
aabb -> a2b2等长，答案仍应是aabb。- 计数只支持一位数字：连续 12 个
a应写成a12，不能把 12 强转成单个字符。- 段结束后没有令
left = right，会重复扫描或陷入死循环。- Go 代码按字节扫描依赖题目“只含英文字母”的约束；若输入可能含多字节字符，应改为按
rune处理。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 443. 压缩字符串 | 中等 | 原地压缩与双指针回填 |
| 1446. 连续字符 | 简单 | 最长连续段长度 |
| 38. 外观数列 | 中等 | 逐轮递推生成描述串 |
| 482. 密钥格式化 | 简单 | 定长分组重排字符串 |
| 58. 最后一个单词的长度 | 简单 | 从末尾定位一段字符 |