题目重点:保留空字符串、数字、冒号和Unicode,不依赖特殊分隔符永不出现。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 本文在Python字符串code point层编码,长度也是code point数量;跨语言/网络应改为UTF-8字节长度与字节解码。
- encode/decode往返保证针对合法编码;示例decode也拒绝截断与非法长度。生产接口需限制声明长度及头部位数。
解题路线
- 每个字段编码为十进制长度、冒号、原样内容。读到冒号解析长度,再严格消费该长度的内容,下一字符即为下个字段头。
- payload里的冒号、数字甚至类似长度头的片段不影响解析,因为payload不靠分隔符终止。
- 空列表编码为空文本;一个空串编码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上失败。
继续深挖
- 流式解析怎样在字段头和内容被任意拆包时保留状态?
- 若内容是任意字节,怎样设计长度上限、版本字段及损坏检测?
