教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」AlgoNoteLeetCode 题解系列中 0271. 字符串的编码与解码 一题的深度展开。该题是一道典型的「设计 数组 字符串」中等难度题目核心挑战在于在不使用任何现成序列化手段的前提下设计一个能将「字符串列表」编码为单个字符串、并能无损还原的编解码算法。读完本文你将掌握长度前缀编码Length-Prefix Encoding的核心思想、完整可运行的 Python 实现、边界用例的验证方法以及如何将其推广到任意字符集的进阶方案。一、题目背景为什么需要自定义编解码题目要求设计一个算法将字符串列表编码成一个可通过网络高效传送的字符串并在接收端解码回原始列表。发送方1 号机与接收方2 号机分别持有如下接口C 原型string encode(vectorstring strs) { // ... your code return encoded_string; }vectorstring decode(string s) { //... your code return strs; }调用流程为1 号机执行encode(strs)得到encoded_string通过网络传送给 2 号机2 号机执行decode(encoded_string)得到strs2要求strs2与发送方的strs完全一致。题目约束1 strs.length 200列表最多包含 200 个字符串。0 strs[i].length 200单个字符串长度可以为 0空串最长 200。strs[i]可能包含256 个有效 ASCII 字符中的任意字符包括数字、大小写字母、标点以及容易被误当作「分隔符」的冒号:、逗号,等。不允许使用任何序列化方法例如eval必须自行设计编码格式。进阶能否编写一个通用算法来处理任何可能的字符集示例示例 1输入[Hello, World]编码传输解码后应得到[Hello, World]。示例 2输入[]一个空字符串组成的列表编码传输解码后应得到[]。示例 2 尤为重要它考察的是对「空字符串」的编码能力。如果编码方案无法区分「空串」与「列表结束」就会在边界用例上出错。二、核心问题如何可靠地区分多个字符串这是一个典型的设计问题。最朴素的想法是把所有字符串直接拼接成一个字符串但这样做会立即遇到两个致命缺陷边界丢失[ab, cd]拼接成abcd解码时无法知道这是两个字符串还是一个字符串abcd。分隔符歧义如果选择逗号,作为分隔符那么[a,b, c]编码为a,b,c后解码时无法判断a,b是内容还是内容 分隔符——因为题目保证字符串可以包含任意 ASCII 字符包括你选定的分隔符本身。核心问题字符串可能包含任何 ASCII 字符包括分隔符我们必须找到一种方法在编码串中明确标识每个字符串的边界并且这种标识本身不能与内容冲突。三、思路一长度前缀编码推荐解法解决方案使用长度前缀编码Length-Prefix Encoding。对于每个字符串str_i将它的长度len_i与内容拼接格式为len_i : str_i。也就是说编码结果是若干个「长度:内容」分组的依次拼接编码结果 5:Hello 5:World 5:Hello5:World解码时读取冒号前的数字得到长度再从冒号后截取该长度的字符即可无歧义地还原每个字符串。编码过程遍历字符串列表strs。对每个字符串str_i计算其长度len_i。将len_i : str_i追加到结果字符串末尾。解码过程使用指针i从头遍历编码后的字符串。在当前位置i之后找到冒号:冒号前的子串即为长度len_i将其转为整数。从冒号后的位置开始向后截取len_i个字符即得到字符串内容。将提取出的字符串加入结果列表将指针移动到内容结束的位置继续处理下一个分组。为什么长度前缀能消除歧义关键在于解码规则是先解析长度、再按长度截取内容长度信息来自冒号前的数字子串与内容无关内容部分由长度严格界定即使内容中包含冒号:或数字也不会干扰长度解析——因为解码器在看到冒号前的内容时会把它视为下一个分组的长度字段起点而不是内容。这一设计使编码串天然具备「自描述self-describing」能力无需依赖任何「内容中不可能出现的保留字符」。四、完整 Python 实现以下实现继承自 encode-and-decode-strings.md 的题解代码并补充了逐步注释class Codec: def encode(self, strs: List[str]) - str: Encodes a list of strings to a single string. Args: strs: 字符串列表 Returns: 编码后的字符串 encoded for s in strs: # 将每个字符串的长度和内容用冒号分隔 encoded str(len(s)) : s return encoded def decode(self, s: str) - List[str]: Decodes a single string to a list of strings. Args: s: 编码后的字符串 Returns: 解码后的字符串列表 decoded [] i 0 while i len(s): # 找到冒号的位置提取长度信息 colon_pos s.find(:, i) length int(s[i:colon_pos]) # 根据长度提取字符串内容 start colon_pos 1 end start length decoded.append(s[start:end]) # 更新指针位置 i end return decoded # Your Codec object will be instantiated and called as such: # codec Codec() # codec.decode(codec.encode(strs))关键实现细节剖析s.find(:, i)从当前位置i开始向后查找冒号返回其下标。由于每个分组都以「数字 冒号」开头冒号必然是当前位置之后第一个冒号find能正确锁定元数据边界。int(s[i:colon_pos])将冒号前的数字子串解析为长度。长度字段的位数随长度变化如0、5、12、200解码端不需要预先知道位数天然支持变长长度字段。i end指针直接跳过「长度 冒号 内容」整个分组进入下一个分组的长度字段循环直到字符串耗尽。空字符串处理空串的长度为0编码为0:解码时length 0截取s[start:start]得到空串边界正确。边界用例验证基于以上实现可以推演以下自测用例均满足题目约束其中示例 1 与示例 2 来自原题输入strs编码结果解码结果[Hello, World]5:Hello5:World[Hello, World][]0:[][]与[]之外的单元素空串列表0:[][a:bc, 12]内容含冒号与数字4:a:bc2:12[a:bc, 12][, , x]多个空串0:0:1:x[, , x]其中「内容含冒号」这一行验证了前文的核心结论4:a:bc2:12解码时第一次找到的冒号是长度4的边界随后严格截取 4 个字符得到a:bc内容中的:不参与任何解析指针跳到2:12继续得到12。这正是长度前缀编码对任意 ASCII 内容的健壮性所在。五、复杂度分析时间复杂度编码O(n)其中n是所有字符串的总长度n sum(len(str_i))。每个字符恰好被扫描并拼接一次另外每个字符串的len()与str()转换均为O(len)量级。解码O(n)只需遍历编码后的字符串一次。每轮find、int、切片的总代价与单个分组长度成正比累加仍为O(n)。空间复杂度O(n)编码结果字符串的长度等于「所有字符串总长度 所有长度字段位数之和 冒号数量」整体仍为O(n)解码结果列表亦为O(n)。在题目约束下列表 ≤ 200 个、单串 ≤ 200 字符n ≤ 40000线性复杂度完全够用。六、进阶思考如何处理任意字符集原题进阶问题「你能编写一个通用算法来处理任何可能的字符集吗」从算法原理出发可以分两层分析当前方案对 ASCII 全字符集的健壮性长度前缀编码完全不依赖「内容中不出现某字符」的假设因此 256 个有效 ASCII 字符含控制字符全部可以安全出现在内容中。这是本方案相比「分隔符转义」类方案的核心优势。向任意字符集推广时的两个注意点长度度量单位要统一编码端len(s)与解码端切片必须使用同一个度量单位。在 Python 中len(str)以 Unicode 码点字符计数切片s[start:end]同样以字符为单位二者天然一致如果底层换成 UTF-8 字节流则必须统一以字节数为单位否则多字节字符会被截断。长度字段本身的自描述性长度数字与冒号是编码协议的一部分只要解码端始终按「先读长度、再取内容」的固定规则解析字符集如何扩展都不会引入歧义。可以认为该方案本身即具备处理任意字符集的能力关键在于保持编码端与解码端对长度单位和分组规则的严格约定。七、延伸对比同属「设计」类的编解码家族在 AlgoNote 的题解体系中0271属于设计类题目与同仓库中其他「设计」标签题目共享解题框架可以横向对照学习0535. TinyURL 的加密与解密同样是encode/decode接口但使用「哈希表 自增 ID」维护长 URL 与短 URL 的映射encode与decode均为O(1)属于「有状态、依赖内存映射」的编码方案而 0271 是无状态、纯格式化的编码方案。二者对比能帮助你理解「格式编码」与「映射编码」的本质区别。0297. 二叉树的序列化与反序列化把二叉树这种非线性结构线性化为字符串同样依赖「分隔符 占位符」的设计思想是本题思路在树结构上的推广难度为困难。0208. 实现 Trie (前缀树) 与 0211. 添加与搜索单词同属设计类题目可一并练习设计题的通用套路。八、在算法通关手册中的位置本篇文章对应的题解原文档位于 docs/solutions/0200-0299/encode-and-decode-strings.md你可以通过以下仓库路径继续深入按编号浏览本章全部题解docs/solutions/0200-0299/index.md查看 0271 题在完整题解总表中的条目docs/00_preface/00_05_solutions_list.md按「设计、数组、字符串」等标签分类检索题目docs/00_preface/00_06_categories_list.md学习 LeetCode 平台刷题流程与规范docs/00_preface/00_04_leetcode_guide.md小结LeetCode 0271 的核心价值在于考察「自定义序列化协议」的设计能力面对可能包含任意字符的字符串列表如何用最少的信息量实现无损编码。长度前缀编码以「长度 冒号 内容」的分组格式把字符串边界信息编码进元数据实现了O(n)时间、O(n)空间的编解码且天然规避了分隔符冲突问题。掌握这一思路你不仅能够解决本题也为理解 RPC 报文、日志聚合、缓存键拼接等真实场景中的「结构化数据序列化」问题打下基础。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 271 字符串编码与解码Encode and Decode Strings长度前缀编码实战与多语言实现LeetCode 271 字符串编码与解码Encode and Decode Strings长度前缀编码实战与多语言实现 导读 本文围绕 LeetCode示例工程教程AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划 导读 本篇是 AlgoNote算法通关手册中 009教程文档知识库String Encode and Decode 字符串编解码全解基于长度前缀与 分隔符的 LeetCode 271 多语言实现String Encode and Decode 字符串编解码全解基于长度前缀与 分隔符的 LeetCode 271 多语言实现 本篇技术指南围绕 LeetC示例工程教程上一篇FreeMove三分钟搞定彻底解决C盘爆满的目录迁移终极方案下一篇QQ音乐格式转换终极指南3步快速解锁你的专属音乐库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考