LeetCode 题解工作台
压缩字符串 III
给你一个字符串 word ，请你使用以下算法进行压缩： 从空字符串 comp 开始。当 word 不为空 时，执行以下操作： 移除 word 的最长单字符前缀，该前缀由单一字符 c 重复多次组成，且该前缀长度 最多 为 9 。 将前缀的长度和字符 c 追加到 comp 。 返回字符串 comp 。 …
1
题型
6
代码语言
3
相关题
当前训练重点
中等 · String-driven solution strategy
答案摘要
我们可以利用双指针，统计每个字符的连续出现次数。假如当前字符 连续出现了 次，然后我们将 划分成若干个 ，每个 最大为 ，然后将 和 拼接起来，将每个 和 拼接起来到结果中。 最后返回结果即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 String-driven solution strategy 题型思路
题目描述
给你一个字符串 word，请你使用以下算法进行压缩：
- 从空字符串
comp开始。当word不为空 时，执行以下操作：- 移除
word的最长单字符前缀，该前缀由单一字符c重复多次组成，且该前缀长度 最多 为 9 。 - 将前缀的长度和字符
c追加到comp。
- 移除
返回字符串 comp 。
示例 1：
输入：word = "abcde"
输出："1a1b1c1d1e"
解释：
初始时，comp = "" 。进行 5 次操作，每次操作分别选择 "a"、"b"、"c"、"d" 和 "e" 作为前缀。
对每个前缀，将 "1" 和对应的字符追加到 comp。
示例 2：
输入：word = "aaaaaaaaaaaaaabb"
输出："9a5a2b"
解释：
初始时，comp = ""。进行 3 次操作，每次操作分别选择 "aaaaaaaaa"、"aaaaa" 和 "bb" 作为前缀。
- 对于前缀
"aaaaaaaaa"，将"9"和"a"追加到comp。 - 对于前缀
"aaaaa"，将"5"和"a"追加到comp。 - 对于前缀
"bb"，将"2"和"b"追加到comp。
提示：
1 <= word.length <= 2 * 105word仅由小写英文字母组成。
解题思路
方法一：双指针
我们可以利用双指针，统计每个字符的连续出现次数。假如当前字符 连续出现了 次，然后我们将 划分成若干个 ，每个 最大为 ，然后将 和 拼接起来，将每个 和 拼接起来到结果中。
最后返回结果即可。
时间复杂度 ，空间复杂度 。其中 为字符串 word 的长度。
class Solution:
def compressedString(self, word: str) -> str:
g = groupby(word)
ans = []
for c, v in g:
k = len(list(v))
while k:
x = min(9, k)
ans.append(str(x) + c)
k -= x
return "".join(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each character is processed once. Space complexity is O(n) since the compressed string comp may store all characters in the worst case. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Ask candidate to explain why cutting smaller prefixes first can lead to longer output.
- question_mark
Check if candidate recognizes maximal same-character prefix strategy.
- question_mark
Probe understanding of handling runs longer than 9 characters efficiently.
常见陷阱
外企场景- error
Cutting prefixes smaller than 9 when a longer run exists, producing non-optimal compression.
- error
Failing to handle consecutive runs longer than 9, causing incorrect counts in comp.
- error
Appending characters without counts when a run length is one, breaking the compression format.
进阶变体
外企场景- arrow_right_alt
Allow compression for mixed-case letters and include case-sensitive counts.
- arrow_right_alt
Limit maximum prefix length to a value other than 9, adjusting the strategy accordingly.
- arrow_right_alt
Compress strings with numbers and letters, extending the character handling logic.