如何设计字符串列表的编码与解码？（LeetCode 271）

简化版

字符串列表编解码不能简单用逗号拼接，因为原字符串里也可能包含逗号。稳妥方案是“长度前缀 + 分隔符 + 内容”：每个字符串编码为 长度#字符串内容。解码时先读到 # 得到长度，再按长度精确截取后面的字符串。这样内容里有任意字符都不会影响边界。

详细版

String encode(List<String> strs) {
    StringBuilder sb = new StringBuilder();
    for (String s : strs) {
        sb.append(s.length()).append('#').append(s);
    }
    return sb.toString();
}

List<String> decode(String data) {
    List<String> ans = new ArrayList<>();
    int i = 0;
    while (i < data.length()) {
        int j = i;
        while (data.charAt(j) != '#') j++;
        int len = Integer.parseInt(data.substring(i, j));
        j++;
        ans.add(data.substring(j, j + len));
        i = j + len;
    }
    return ans;
}

长度前缀负责告诉解码器下一个字符串有多长。
# 只分隔长度和内容，不分隔字符串内容本身。
内容中即使包含 #、逗号、空格、空字符串，也能正确恢复。
编码和解码都是 O(totalLength)。

完整版教学

一、为什么简单 join 不可靠

如果用逗号拼接：["a,b","c"] 会编码成 "a,b,c"，解码时无法判断它原来是 ["a","b","c"] 还是 ["a,b","c"]。任何固定分隔符都有同样问题，因为原字符串可能包含这个分隔符。

这道题真正考的是“如何设计无歧义协议”。编码结果必须让解码器在没有额外上下文的情况下唯一恢复原列表。

二、长度前缀为什么无歧义

长度前缀把边界从“遇到某个字符停止”改成“读取固定数量字符”。格式可以定义为：

<len>#<content><len>#<content>...

例如：

["leet", "co#de", ""]
编码为：4#leet5#co#de0#

解码第一个字符串时读到 4#，就知道后面 4 个字符是内容 leet；第二个读到 5#，即使内容里有 #，也按长度取 5 个字符 co#de；第三个长度为 0，取空串。

记忆钩子：分隔符只负责结束“长度字段”，字符串内容靠长度切，不靠分隔符猜。

三、编码过程怎么保证可解析

编码时每个字符串都输出三个部分：十进制长度、固定符号 #、原始内容。长度字段只包含数字，因此 # 能可靠标记长度结束。内容原样追加，不需要转义。

s = "ab#c"
len = 4
片段 = "4#ab#c"

解码器看到第一个 # 后，已经知道内容长度是 4，所以后面的 # 不会被误认为分隔符。

四、解码过程的指针语义

解码用指针 i 指向当前片段开头。先用 j 找到下一个 #，data[i..j-1] 是长度字段。解析出 len 后，内容起点是 j+1，内容终点是 j+1+len。

data = 4#leet5#co#de0#
i=0, j=1, len=4, 取 [2,6) -> leet, i=6
i=6, j=7, len=5, 取 [8,13) -> co#de, i=13
i=13, j=14, len=0, 取 [15,15) -> "", i=15

每次循环都完整消费一个字符串片段，因此不会混乱。

五、和转义方案的对比

方案	思路	优点	缺点
固定分隔符	用逗号或 `#` 分隔	简单	内容含分隔符时歧义
转义分隔符	内容中的分隔符写成转义序列	可行	解码复杂，转义字符本身也要处理
长度前缀	先写长度，再按长度读取	无歧义，代码稳定	需要解析长度字段

面试中长度前缀最推荐，因为它像网络协议里的 frame：先告诉包体长度，再读包体。

六、复杂度与边界

设所有字符串总长度为 T。编码遍历每个字符串一次，输出长度字段和内容，时间 O(T)，空间 O(T) 用于结果。解码同样线性扫描编码串，时间 O(T)，输出列表占用 O(T)。

边界要覆盖：

[] -> ""
[""] -> "0#"
["#"] -> "1##"
["a,b", ""] -> "3#a,b0#"

空列表和包含空字符串不是同一回事：空列表编码为空串；一个空字符串编码为 0#。

七、常见误区与追问

误区：用逗号 join 后 split。 原字符串可能含逗号，无法无歧义恢复。
误区：认为 # 不会出现在输入中。 题目通常允许任意字符，不能靠假设逃避协议设计。
误区：解码时遇到内容里的 # 就截断。 # 只用于长度字段结束，内容靠长度截取。
追问：空字符串怎么处理？ 编码为 0#，解码时截取长度 0 的内容。
追问：空列表和一个空字符串如何区分？ 空列表编码为空串；一个空字符串编码为 0#。
追问：长度字段很大怎么办？ 按语言整数范围处理；真实系统协议还会限制最大帧长度防止异常输入。

八、加强记忆

字符串列表编解码的核心是无歧义边界。固定分隔符会被内容污染，长度前缀不会：写成 len#content，解码时先读长度，再按长度切内容。# 不是内容分隔符，只是长度字段结束标记，因此内容里出现任何字符都能恢复。

简化版

详细版