字符串的编码与解码Encode and Decode Strings光看题目名很难让人紧张起来。我第一次刷到它的时候心里想的是这不就是把字符串数组拼成一个字符串再拆回来吗三五分钟就能写完。可后来在一次模拟面试里我用最朴素的写法交上去面试官随口问了一句“如果某个字符串里恰好包含你的分隔符呢”我当场就愣住了。也是从那次之后我才认真琢磨这道题发现它根本不是什么开胃菜而是一道被严重低估的、串联起字符串处理、边界条件、甚至网络协议设计的题目。如果你正在刷题或者需要在项目里设计一个传输协议这篇内容应该能帮你少走一些弯路——因为它把“字符串的边界划分”这件事讲透了。1. 十秒写出来的分隔符方案为什么注定翻车1.1 第一反应join 一下不就完了吗大多数人的第一版代码长这样def encode(strs): return ,.join(strs) def decode(s): return s.split(,)当输入是[hello, world]时encode得到hello,worlddecode还原出两个字符串一切都很美好。然后你把[hello,world, another]丢进去就会得到hello,world,anotherdecode出来变成三个字符串。你的协议把两个元素变成了三个数据直接错乱。有人会说那我把分隔符换成不怎么出现的符号比如\n、|或者某些控制字符。这种“换分隔符”的做法本质是在赌输入里不会出现某个字符。对在线评测来说测试用例一旦包含这个字符就完蛋对工程来说用户的输入永远比你想象的离谱。你写一个日志采集系统日志行内出现竖线太正常了我后面还会讲到这个真实案例。所以问题从来不是“选哪个分隔符”而是“分隔符方案本身把内容字符和结构字符混在了同一个符号空间里”。还有个更隐蔽的错误有些人会把所有字符串直接拼在一起然后约定每个字符串固定长度比如 4 字节decode时每 4 字节切一段。这要求所有输入等长变长输入一进来就错位。本质上也是把“结构信息”写死在了假设里一旦假设不成立解析就全线崩溃。1.2 翻车的本质是协议产生了歧义“编码加解码”本质上是在设计一个协议。协议合格的最基本标准是任何两个不同的输入都不能编码出同一个输出而且给定输出解码必须能无歧义地还原出唯一的原始输入。这一点看起来理所当然但很多第一版代码都做不到。方案编码示例翻车场景逗号分隔[a,b,c] - a,b,c解码成[a,b,c]换行分隔[a,b\nc] - a\nb\nc解码成[a,b,c]固定长度假设每串 4 字节长度不匹配时直接错位转义加分隔[a#,#b] - a#####b连续#导致分界点错乱分隔符方案失败的根本原因是内容字符集和结构字符集没有隔离。你在字节流里放了一个逗号它到底是“数据里的逗号”还是“字段之间的逗号”没有额外的规则解码器无法判断。有人可能会说那选一个二进制里不可能出现的字符当分隔符不就行了。但在“字符串”这个抽象概念面前输入可以是任何字符包括你精心挑选的“不可能字符”。真正的解法是把结构信息和内容信息分开存放——这就是下一章要展开的思路。1.3 转义方案看似聪明实则要维护一套状态机有人说那把分隔符转义掉不就行了以#作为分隔符、内容中的#替换成##为例我见过很多人写出这种代码def encode(strs): return #.join(s.replace(#, ##) for s in strs) def decode(s): # 直觉上应该先按 # 切分再把 ## 还原成 # ...看起来无懈可击但拿[a#, #b]一测就会发现问题编码结果是a#####b解码时##成对还原之后剩下的单个#到底算分隔符还是转义残留规则非常微妙捋不清楚。正确的转义方案通常要引入第二个转义字符比如用\#表示内容中的#、\\表示反斜杠然后解码时逐字符扫描、再逐段反转义。它能用但编码后的字符串肉眼不可读长度会膨胀解码状态机也复杂得多。如果题目只允许用“一个分隔符”做变体转义是唯一出路但在一般情况下长度前缀方案是更干净、更不容易出错的答案。2. 真正能打的编码方案长度前缀与自描述协议2.1 为什么长度前缀是这类问题的标准答案思路一句话每个字符串前面写上它的长度再写一个把“长度数字”和“内容”隔开的标记。比如hello-5#helloworld-5#world整个数组 -5#hello5#world解码时从开头扫描到第一个#把前面的数字解析成长度 L然后从#后面取 L 个字符这就是第一个字符串取完之后继续解析下一段。整个过程中字符串内容里有什么都不会影响解析因为字节流是先给长度再给内容内容再怪异读取的边界都已经被长度固定住了。打个比方。分隔符方案像是在一堆货物之间贴胶带做标记货物上恰好有同样的胶带就乱套长度前缀方案则像附了一张清单每件货物都写着“这件货物长度是 5内容是 hello”仓库管理员只要按清单读数永远不会拿错。这种方案通常被称为“自描述协议”因为每一条数据都随身携带了描述自身的长度信息不需要依赖外部规则来切分。这里的关键认知转变是#不是用来分割字符串的而是用来分割“长度数字”和“字符串内容”的。它出现在每一组“长度加内容”的内部因此即使内容里有#也不会被误认成边界。结构信息和内容信息被明确分开了歧义就消失了。2.2 可直接抄走的实现Python 与 C先给 Python 版本class Codec: def encode(self, strs): return .join(f{len(s)}#{s} for s in strs) def decode(self, s): res [] i 0 while i len(s): j s.find(#, i) length int(s[i:j]) i j 1 res.append(s[i:i length]) i length return resdecode里没有出现对内容字符的判断完全依靠长度移动指针。注意find找的是“下一个#”而它一定属于下一组长度前缀不会在内容里迷路因为上一段的内容长度已经被消费掉了。空字符串编码成0#解码时长度取 0切片为空串指针不前进也不后退继续解析下一个块。再给一个 C 版本class Codec { public: string encode(vectorstring strs) { string res; for (const string s : strs) { res to_string(s.size()) # s; } return res; } vectorstring decode(string s) { vectorstring res; size_t i 0; while (i s.size()) { size_t pos s.find(#, i); if (pos string::npos) break; int len stoi(s.substr(i, pos - i)); i pos 1; res.push_back(s.substr(i, len)); i len; } return res; } };C 默认按字节取size()在纯 ASCII 输入下没问题如果内容里有中文长度单位就需要重新定义这个坑放到第三章细说。另外encode里逐串拼接在输入特别大时会有多次扩容拷贝面试时可以主动提一句“先用循环统计总长度再reserve预留容量”这个细节很加分。2.3 前缀分隔符的选择与复杂度分析为什么用#而不是空格或者逗号这其实是约定俗成关键要求是它不能出现在长度数字里。数字字符是 0 到 9#不在其中所以解码时find(#)遇到的一定是长度数字的结束。用:、;甚至空格也都能工作只是空格会让编码结果难以肉眼检查所以大多数人习惯选一个视觉上不易混淆的符号。更严谨的工程实现里长度部分不一定用“十进制数字加分隔符”而是用定长整数比如固定 4 字节或变长整数类似 varint每个字节用最高位标记是否继续。这些做法在二进制协议里更常见文本算法题里用十进制就足够了。但理解这个设计层次很重要长度信息的表示方式是可以替换的核心思想“先告诉对端读多少字节”始终不变。复杂度也值得说清楚。设所有字符串总字符数为 N。encode扫描每个字符并拼接时间是 O(N)。decode里每次find从当前指针开始找下一个#找到的位置严格递增所有find扫描过的区间互不重叠所以总时间也是 O(N)。额外空间除了返回结果只有几个指针和临时变量是 O(1)。两个方向都已经是最优复杂度因为每个字符至少要读一次、写一次。3. 边界条件才是题眼空串、空数组、Unicode 与非法输入3.1 空字符串和空数组必须能区分开很多人的方案挂在这里encode([])返回空串encode([])用join也返回空串结果decode收到空串时根本不知道要还原成[]还是[]。长度前缀方案天然区分原始输入编码结果解码结果[][][]0#[][, ]0#0#[,]有人可能觉得“空数组和空字符串数组”这种边界太抠字眼但在真实系统里这对应着“没有缓存”和“缓存了一个空结果”的区别。很多缓存穿透问题就是因为序列化方案没区分这两者导致空结果回源打爆后端。所以这个边界不是面试官刁难是真实工程里就存在的需求。实现上也有个容易翻车的细节decode对空串和0#都必须正确处理。Python 的find如果找不到#会返回 -1当我们把它当成切片索引时会产生各种诡异行为。合法输入下循环会在i len(s)时停下来但如果你要写防御性代码就得显式检查j -1的情况。3.2 字符串里出现 # 和数字开头也没事拿一个狠一点的例子实测一下。假设输入是[a#b, #, 12#3]编码过程a#b长度为 3得到3#a#b#长度为 1得到1##12#3长度为 4得到4#12#3拼接起来是3#a#b1##4#12#3。解码过程读3#知道第一个字符串长度是 3从#后取a#b指针移动到1##读1#取#指针移动到4#12#3读4#取12#3内容里的#和数字前缀丝毫没有干扰解析因为每次读取的边界完全由长度决定。这也是长度前缀方案鲁棒性优于分隔符方案的根本原因它不需要对内容做任何假设所有内容都是“黑盒”。这一点在真实协议里太重要了因为你永远无法保证用户数据里不会出现某个特殊字符。3.3 Unicode、多字节字符与“长度”的定义这里有一个特别隐蔽的坑不同语言、不同运行时对“字符串长度”的定义不一样。C 的std::string::size()返回字节数Python 的len(str)返回 Unicode 码点数Java 的String.length()返回 UTF-16 code unit 数量。同一个中文句子在三种语言里算出的长度可能不同。如果encode用 C 按字节写长度前缀decode用 Python 按码点去取子串中文内容一进来就会错位。我后面会讲一个真实案例这里先说结论设计跨语言协议时最稳妥的做法是先把字符串编码成 UTF-8 字节流然后长度按“UTF-8 字节数”计算。这其实也是绝大多数现代网络协议的选择——把字符问题降到字节层面通信双方就都只有一个尺子。如果算法题的输入限定 ASCII这一节可以略过但面试官如果追问“输入是中文怎么办”能答出“统一按 UTF-8 字节数算”并且解释为什么这样做会是很亮眼的加分项。3.4 防御性解码非法格式怎么办在线评测的测试用例通常保证输入合法但协议设计者不能这么天真。一个健壮的decode至少要考虑三类非法输入字符串里没有#比如abc长度前缀无法解析长度字段不是数字比如x#abc长度字段是数字但越界比如99#ab声称长度 99实际内容只有 2 个字符。处理策略也有层次抛异常、返回错误码、尽力恢复。大多数序列化框架选择抛异常因为数据已经不可信继续解析只会产生更离谱的结果。更严格的协议还会在帧头加一个魔数、校验和、版本号帮助你快速识别错位帧。这就是从这道题走向工程设计的自然延伸也是我在第四章想展开的内容。如果你在面试中写出防御版本哪怕只是判断find返回值和边界越界都很容易让面试官眼前一亮。因为这表明你不只是会写“快乐路径”脑子里有真实系统的那根弦。4. 从算法题到生产协议边界划分无处不在4.1 真实协议里的长度前缀从内存数据库到 RPC 帧很多人不知道这道题的抽象几乎就是一堆真实协议的原型。举个例子某类以文本协议著称的内存数据库传输一条字符串时用的是形如$字节长度\r\n数据\r\n的格式。比如$5\r\nhello\r\n表示字符串hello。如果要传输一个字符串数组就连续写多个这样的块接收方每次先读一个块再从长度得知该读多少数据。这和我们的encode/decode完全是一个思路只是把#换成了\r\n把文本字符串换成了字节流。RPC 和消息队列领域更常见的是二进制帧开头固定 4 个字节存长度通常是大端序后面跟着 payload。接收方先读 4 字节得到长度 L再读 L 字节然后继续读下一个 4 字节。这就是一个标准的消息边界划分过程。你可以把这个过程直接理解成数组的每个元素被一个“长度前缀”包裹着依次排列在字节流里。4.2 为什么工程协议普遍偏爱长度前缀拿分隔符方案和长度前缀方案做一个系统对比维度分隔符方案长度前缀方案边界定位必须扫描匹配分隔符读长度后直接跳跃内容限制需要对分隔符转义内容任意无需转义随机访问整体扫描才能定位到字段可以按帧头算偏移编码膨胀转义可能导致明显膨胀每串只多几个字节前缀可读性人类可直接阅读需要工具或心智解析分隔符方案最大的优势是人类可读、调试方便比如 CSV 就是这样但在二进制协议、高吞吐场景、不可信内容面前长度前缀几乎是默认选择。它也有自己的软肋一旦长度字段被写坏后续整个字节流都会错位而且很难自恢复。所以工程协议通常会在长度附近再加一个魔数或者校验和用来尽可能早地发现错位帧。这些都是在“长度前缀”这个骨架上长出来的血肉但骨架永远是那道算法题的骨架。4.3 题目的常见变体禁止数字前缀、二进制内容、最短编码面试里这道题经常被改条件最常见的有三类。第一类要求只能用一个分隔符完成编码。那就只能走转义路线。通常做法是引入一个转义字符比如用\#表示内容里的#、\\表示反斜杠。编码时先对\转义再对#转义然后仍然用#作为分隔符连接解码时按分隔符拆开再逐段反转义。它能工作但规则需要严丝合缝少定义一个情况就会出 bug。第二类输入不是字符串而是任意二进制字节串。这时“长度”只能按字节算编码结果也不能再用普通可打印字符串表示而是一个字节序列先写长度再写 payload。这就是二进制协议的标准形态。很多人没意识到从这道题的文本版本到二进制版本差的只是把str换成bytes/byte[]核心设计完全一样。第三类要求编码结果尽可能短。十进制长度前缀太浪费可以用变长整数每个字节用 7 位存长度最高位表示“是否还有后续字节”。短字符串只花 1 个字节存长度长字符串根据字节数递增。这类变体就是你从算法题走向“序列化协议设计”的一道门值得玩一玩。不管怎么变核心决策始终是用什么样的结构信息来区分数据边界以及这个结构信息本身如何被无歧义地解析。想通了这道题这些变体就都只是画皮。5. 被低估的原因以及我踩过的几个真坑5.1 面试里这道题到底在考什么这道题没有刁钻的算法没有复杂的数据结构不背模板也写得出基础版本所以很多人刷题时直接跳过。但真正做过面试官的人都知道正因为基础它反而适合观察候选人的思维颗粒度。你写出的encode和decode暴露的是你对“协议设计”的基本功有没有考虑空输入内容撞上分隔符怎么办长度用什么单位非法输入怎么处理要不要做校验一道题能串起这么多追问在入门级别里相当少见。它其实是“系统设计面试”的微缩版题目给你一个对象要求你把它序列化到一条数据流里再反序列化还原。这个能力在缓存、消息队列、RPC、存储引擎里天天都要用。所以它被低估不是因为题目本身简单而是因为很多人把它当成字符串题而不是序列化题来对待。5.2 我在实际项目中踩过的两个编码坑第一个坑和竖线有关。有段时间我在做一个日志采集模块为了省事用|作为字段分隔符把日志行拆成若干个字段。模块上线第二天就有人反馈部分日志字段错乱排查到最后发现是某些业务日志自身含有竖线解析器把一条消息劈成了两条。后来我把协议改成了长度前缀每个字段前面先写一个十进制长度再写内容。上线之后这个类型的问题再也没有出现过。这件事给我的教训是可读的协议不一定可靠可靠的协议不一定第一眼可读。第二个坑是多字节长度不一致。一个内部服务用 C 实现客户端用 Python 实现。服务端写入消息时按字节数生成长度前缀客户端却按字符数去切片英文消息一切正常中文消息偶尔截断乱码。两边排查了很久才发现是对“字符串长度”的定义不一致。最后统一在应用层先做 UTF-8 编码长度一律按编码后的字节数计算问题才彻底解决。这个坑如果不是亲身经历光靠看文档真的很难预判。5.3 说给准备面试的人三个练习建议如果你想把这题吃透我建议不要止步于通过测试用例而是再做三件事。第一自己构造一组边界测试用例空数组、只有空串的数组、包含大量#和数字开头的数组、超长字符串、包含中文的字符串。一个实现能经受住这些用例才算合格。第二不要只写代码练习用语言表达设计决策。面试官问你“为什么不用分隔符”“长度单位为什么选字节”你要能在一分钟内给出清晰的权衡分析而不是“我觉得这样写能过”。能说出 trade-off 和不能说出 trade-off在面试官眼里是两个完全不同的级别。第三把它和序列化、协议问题联系起来。去了解一个真实文本协议比如那个$长度\r\n数据\r\n的格式再去看一个二进制帧结构然后回头审视你自己的实现想想它还缺哪些生产级要素校验、版本、逃逸、性能优化。想完这一圈这道题在你手里就已经从一道小题变成了一节系统设计课。