SWE · Stage 3 Coding

Oracle 连续字符压缩:单个原样,重复后接次数

按题目从左到右分组连续字符,处理空串、多位数次数、非连续重复和编码歧义。

题目重点:按题目从左到右分组连续字符,处理空串、多位数次数、非连续重复和编码歧义。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 按 Python 字符逐个处理的训练版;若题目规定字节、Unicode grapheme cluster 或大小写归一化,需重新确认。
  • 题目只要求压缩,未要求结果一定比原串短,也未要求可无歧义解码;数字字符会让无分隔符格式有解码歧义。

解题路线

  1. 维护当前 run 起点,向右扫描直到字符变化或字符串结束;run 长度为 end−start。
  2. 长度 1 追加原字符,长度大于 1 追加字符与十进制长度;然后从新字符开始下一 run。
  3. 循环不变量是 start 之前的字符已被完整编码,start 到 end−1 都等于当前字符;每个字符只作为 run 成员扫描一次。

手动走一遍

aaaaabbbccca 的 runs 为 a×5、b×3、c×3、a×1,输出 a5b3c3a。末尾 a 与开头 a 不相邻,不能合并。

Python 参考实现

下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。

代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。

"""Compress consecutive character runs; a run of one stays unchanged."""


def compress_runs(value: str) -> str:
    if not value:
        return ""
    parts = []
    start = 0
    for end in range(1, len(value) + 1):
        if end == len(value) or value[end] != value[start]:
            count = end - start
            parts.append(value[start] if count == 1 else value[start] + str(count))
            start = end
    return "".join(parts)

复杂度

N 个字符 O(N) 扫描,输出构造占 O(M) 空间,M 为编码结果长度;用片段列表最后 join 避免重复字符串拼接可能造成平方时间。

易错点与追问

容易失分的边界

  • 把全局字符频次当连续 run 计数。
  • 忘记处理最后一段或空串。
  • 声称这种编码一定可逆:若原文含数字,无分隔符和转义规则可能产生歧义。

继续深挖

  • 如果要保证可解码,如何加转义、长度前缀或限制原始字符集?
  • 若要求只有压缩后更短才返回压缩串,如何避免重复遍历?
✓已复制微信号!