SWE · Coding

字符串列表序列化:长度前缀避免分隔符冲突

保留空字符串、数字、冒号和Unicode,不依赖特殊分隔符永不出现。

题目重点:保留空字符串、数字、冒号和Unicode,不依赖特殊分隔符永不出现。

题意与假设

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

  • 本文在Python字符串code point层编码,长度也是code point数量;跨语言/网络应改为UTF-8字节长度与字节解码。
  • encode/decode往返保证针对合法编码;示例decode也拒绝截断与非法长度。生产接口需限制声明长度及头部位数。

解题路线

  1. 每个字段编码为十进制长度、冒号、原样内容。读到冒号解析长度,再严格消费该长度的内容,下一字符即为下个字段头。
  2. payload里的冒号、数字甚至类似长度头的片段不影响解析,因为payload不靠分隔符终止。
  3. 空列表编码为空文本;一个空串编码0:,二者可区分。若要求规范编码唯一,需拒绝长度头前导零,当前解码器允许。

手动走一遍

["", "a:b", "猫🙂"]编码0:3:a:b2:猫🙂,顺序与内容完全恢复。2:a声明两字符却只有一字符,必须拒绝;2::a合法payload为:a。

Python 参考实现

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

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

def encode(strings):
    return ''.join(str(len(s)) + ':' + s for s in strings)


def decode(text):
    result, i = [], 0
    while i < len(text):
        colon = text.find(':', i)
        if colon < 0 or colon == i or any(c not in '0123456789' for c in text[i:colon]):
            raise ValueError("invalid length")
        size = int(text[i:colon])
        i = colon + 1
        if size > len(text) - i:
            raise ValueError("truncated payload")
        result.append(text[i:i + size])
        i += size
    return result

复杂度

设内容总长L、字段数n,encode/decode需O(L+Σlog(length+1))时间与输出空间;大长度十进制解析的位复杂度另计。

易错点与追问

容易失分的边界

  • 用split(":")会拆坏包含冒号的payload。
  • JS length计UTF-16单位而Python计code point,跨端直接比较会在emoji上失败。

继续深挖

  • 流式解析怎样在字段头和内容被任意拆包时保留状态?
  • 若内容是任意字节,怎样设计长度上限、版本字段及损坏检测?
✓已复制微信号!