LeetCode 题解工作台
压缩字符串
给你一个字符数组 chars ，请使用下述算法压缩： 从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ： 如果这一组长度为 1 ，则将字符追加到 s 中。 否则，需要向 s 追加字符，后跟这一组的长度。 压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
class Solution: def compress(self, chars: List[str]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
- 如果这一组长度为
1，则将字符追加到s中。 - 否则，需要向
s追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
注意：数组中超出返回长度的字符无关紧要，应予忽略。
示例 1：
输入：chars = ["a","a","b","b","c","c","c"] 输出：6 解释："aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。
示例 2：
输入：chars = ["a"] 输出：1 解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。
示例 3：
输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] 输出：4 解释：由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。
提示：
1 <= chars.length <= 2000chars[i]可以是小写英文字母、大写英文字母、数字或符号
解题思路
方法一
class Solution:
def compress(self, chars: List[str]) -> int:
i, k, n = 0, 0, len(chars)
while i < n:
j = i + 1
while j < n and chars[j] == chars[i]:
j += 1
chars[k] = chars[i]
k += 1
if j - i > 1:
cnt = str(j - i)
for c in cnt:
chars[k] = c
k += 1
i = j
return k
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each character is read and written at most once. Space complexity is O(1) as all operations are performed in-place without using extra arrays. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Are you using a read and write pointer to compress without extra space?
- question_mark
How do you handle counts that are larger than 9 when writing them back?
- question_mark
Can you guarantee that your method overwrites the array correctly and maintains proper length?
常见陷阱
外企场景- error
Forgetting to split counts larger than 9 into separate digits.
- error
Overwriting characters before processing all in a group, causing incorrect compression.
- error
Using extra space instead of modifying the array in-place, violating problem constraints.
进阶变体
外企场景- arrow_right_alt
Compress strings where only certain characters need counting, e.g., vowels.
- arrow_right_alt
Allow compression using a delimiter instead of counts, changing in-place logic slightly.
- arrow_right_alt
Handle arrays with non-alphabetic symbols while maintaining the same two-pointer scanning approach.