String Encode and Decode 字符串编解码全解基于长度前缀与#分隔符的 LeetCode 271 多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 271「字符串的编码与解码Encode and Decode Strings」展开核心方案是长度前缀Length-Prefix编码将每个字符串的长度写在内容之前并用#作为长度与内容的边界分隔符从而把任意字符串列表压缩为单个字符串、再无损还原。文章以仓库中的 hints/string-encode-and-decode.md 提示文档为骨架结合 articles/string-encode-and-decode.md 完整题解与0271-encode-and-decode-strings.*系列源码覆盖 Python / Java / C / JavaScript / TypeScript / Go / Rust / Ruby / Swift / Kotlin / C# 共 11 种语言讲解两种编码架构、边界条件与复杂度推导。读完你将掌握一套不依赖任何特殊字符、可安全编码任意 Unicode 内容的字符串序列化方案并能在实际系统中直接复用。1. 问题定义与复杂度目标该题要求设计两个函数encode(strs: List[str]) - str把字符串列表编码成一个字符串decode(s: str) - List[str]把编码后的字符串还原成原始列表。核心约束是原始字符串中可能包含任意字符逗号、换行、数字、#、空字符串等编码结果必须能够被无损、无歧义地还原。仓库中的提示文档 hints/string-encode-and-decode.md 给出了明确的目标复杂度时间复杂度每次encode()与decode()调用均为O(m)其中m为所有字符串长度之和空间复杂度O(m n)其中n为字符串个数m为总长度。文章 articles/string-encode-and-decode.md 的复杂度小节进一步细化为O(m n)时间与空间。两种表述的差异在于是否把拼接每个字符串前缀的固定开销O(n)计入本质一致编码与解码都必须线性扫描全部输入内容且编码结果本身的规模就是O(m n)。2. 朴素思路的缺陷为什么不能只用分隔符提示文档的Hint 1指出一种朴素做法是使用一个非 ASCII 字符作为分隔符。你能想到更好的方式吗join 分隔符是最直观的思路但存在致命缺陷当原始字符串内部出现与分隔符相同的字符时解码将产生歧义。以逗号为例输入[a,b, c]会被编码成a,b,c解码时无法区分它究竟是[a,b, c]还是[a, b, c]。即使改用非 ASCII 字符如\u0101也只是降低了冲突概率并没有从数学上消除歧义——只要输入内容可以任意冲突就仍然可能发生。JavaScript 源码 javascript/0271-encode-and-decode-strings.js 中保留了这一朴素变体var encode (strs, nonASCIICode String.fromCharCode(257)) { return strs.join(nonASCIICode); }; var decode (strs, nonASCIICode String.fromCharCode(257)) { return strs.split(nonASCIICode); };该实现刻意使用 ASCII 范围之外的字符String.fromCharCode(257)作为分隔符试图避开内容冲突——但注释也标明它只是作为一种对照思路存在。仓库的主推实现仍然是下面的长度前缀方案。3. 核心思路长度前缀Length-Prefix编码提示文档的Hint 2与Hint 3给出了完整思路Hint 2基于每个字符串的长度进行编码与解码并思考如何区分「长度数字」与「字符串中可能出现的数字」Hint 3采用「长度数字 分隔符# 字符串本身」的编码形式。解码时先读取数字直到遇到#再用该数字读取指定数量的字符作为原始字符串。这一方案的精妙之处在于长度数字本身成为字符串的「边界标记」#只负责分隔长度与内容而内容区完全不需要转义。无论字符串里出现什么字符包括#、,、数字、换行解码器都严格按照长度取字符因此内容对解析逻辑完全「透明」。编码示例输入[hello, world]5#hello5#world解码流程从位置 0 读到#得到长度5跳过#取接下来 5 个字符得到hello指针移到world起始处重复上述过程得到5与world。4. 方案一集中存储长度段文章给出的第一种实现articles/string-encode-and-decode.md 先给出了一种「两段式」实现把所有长度集中写在最前面用逗号分隔再用#标记长度段结束最后拼接全部原始字符串。编码步骤输入列表为空时直接返回空字符串遍历所有字符串收集各自的长度将长度用逗号连接追加#标记长度段结束依次追加全部原始字符串返回拼接结果。解码步骤编码串为空时返回空列表从开头逐个字符读取直到遇到#期间按逗号切分出全部长度跳过#后按长度列表依次截取对应字符数作为子串返回解码列表。Python 实现articles/string-encode-and-decode.md 原文class Solution: def encode(self, strs: List[str]) - str: if not strs: return sizes, res [], [] for s in strs: sizes.append(len(s)) for sz in sizes: res.append(str(sz)) res.append(,) res.append(#) res.extend(strs) return .join(res) def decode(self, s: str) - List[str]: if not s: return [] sizes, res, i [], [], 0 while s[i] ! #: j i while s[j] ! ,: j 1 sizes.append(int(s[i:j])) i j 1 i 1 for sz in sizes: res.append(s[i:i sz]) i sz return res注意该方案的编码结果形如5,5#helloworld。它通过,分隔多个长度、用#把「长度段」和「内容段」隔开。Swift 仓库实现 swift/0271-encode-and-decode-strings.swift 采用了与此几乎相同的两段式结构长度用逗号连接#结束长度段并在编码空列表时返回#而非空串作为「空列表」的显式哨兵class Codec { func encode(_ strs: [String]) - String { if strs.isEmpty { return # } var counts [String]() for str in strs { counts.append(\(str.count)) } return counts.joined(separator: ,) # strs.joined() } func decode(_ s: String) - [String] { if s # { return [] } let index s.firstIndex(of: #)! let counts String(s[s.startIndex...s.index(before: index)]).components(separatedBy: ,) var sIndex s.index(after: index) var decodedStrings [String]() for count in counts { let endIndex s.index(sIndex, offsetBy: Int(count)! - 1) if sIndex endIndex { decodedStrings.append() continue } decodedStrings.append(String(s[sIndex...endIndex])) sIndex s.index(after: endIndex) } return decodedStrings } }该方案正确但「长度段」与「内容段」分离的结构稍显绕——它需要先用,解析完所有长度再回到内容段逐个截取维护的指针状态更多。因此文章随即给出了更简洁的优化版本。5. 方案二推荐逐串length#string编码articles/string-encode-and-decode.md 的「Encoding Decoding (Optimal)」小节给出了更优雅的写法不再集中存放长度而是把每个字符串的长度紧跟其内容形成length#string的成对序列。编码步骤初始化结果构建器或字符串部件列表对每个字符串计算长度 → 追加长度→ 追加#→ 追加字符串本身返回拼接结果。解码步骤初始化结果列表与指针i 0当i未越界时循环用指针j从i出发向后扫描直到遇到#s[i:j]即为长度将s[i:j]解析为整数lengthi移到#后一位截取s[i : i length]作为原始字符串加入结果i前进length继续解析下一段返回结果列表。以[neet, code, love, you]为例编码结果为4#neet4#code4#love3#you解码时从左到右读4→ 取neet→ 读4→ 取code→ 依次还原全部四个字符串。5.1 各语言实现对照文章题解与仓库源码在 11 种语言中实现了同一算法以下选取具有代表性的几种Pythonpython/0271-encode-and-decode-strings.pyclass Solution: def encode(self, strs): res [] for s in strs: res.append(str(len(s))) res.append(#) res.append(s) return .join(res) def decode(self, s): res [] i 0 while i len(s): j i while s[j] ! #: j 1 length int(s[i:j]) i j 1 j i length res.append(s[i:j]) i j return resJavajava/0271-encode-and-decode-strings.java解码时用i j 1 length一步跨过#与内容区再以str.substring(j 1, i)取出字符串public class Solution { public String encode(ListString strs) { StringBuilder encodedString new StringBuilder(); for (String str : strs) { encodedString.append(str.length()).append(#).append(str); } return encodedString.toString(); } public ListString decode(String str) { ListString list new ArrayList(); int i 0; while (i str.length()) { int j i; while (str.charAt(j) ! #) j; int length Integer.valueOf(str.substring(i, j)); i j 1 length; list.add(str.substring(j 1, i)); } return list; } }Ccpp/0271-encode-and-decode-strings.cpp使用to_string(size())生成长度前缀stoi反向解析。TypeScripttypescript/0271-encode-and-decode-strings.ts编码用模板字符串${str.length}#${str}一行完成解码用slice按长度截取function encode(strs: string[]): string { return strs.map((str) ${str.length}#${str}).join(); } function decode(str: string): string[] { let decodedWords: string[] []; let i 0; while (i str.length) { let j: number i; while (str[j] ! #) { j; } let len: number parseInt(str.slice(i, j), 10); decodedWords.push(str.slice(j 1, j 1 len)); i j 1 len; } return decodedWords; }Rubyruby/0271-encode-and-decode-strings.rb编码同样是一行式strs.map { |str| #{str.length}##{str} }.join。Gogo/0271-encode-and-decode-strings.go注意该仓库实现把分隔符换成了|并在解码时手工按位累乘还原长度数字l (int(strs[j]) - 48) * dec展示了同一算法的字符级实现func (codec *Codec) Encode(strs []string) string { defer codec.b.Reset() for _, word : range strs { codec.b.WriteString(strconv.Itoa(len(word))) codec.b.WriteRune(|) codec.b.WriteString(word) } return codec.b.String() } func (codec *Codec) Decode(strs string) []string { var words []string for i : 0; i len(strs); { lenStart : i lenEnd : i for strs[lenEnd] ! | { lenEnd } var l int dec : 1 for j : lenEnd - 1; j lenStart; j-- { l (int(strs[j]) - 48) * dec dec * 10 } start : lenEnd 1 end : start l words append(words, string(strs[start:end])) i end } return words }Rustrust/0271-encode-and-decode-strings.rs采用了另一个可复用的变体把长度作为单个字节s.len() as u8直接写入编码串解码时读一个字节得到长度再截取内容——因为u8上限 255该变体仅适用于单串长度不超过 255 的场景fn encode(self, strs: VecString) - String { let mut store String::new(); for s in strs{ let len s.len() as u8; store.push(len as char); store.push_str(s); } store } fn decode(self, s: String) - VecString { let s: Vecchar s.chars().collect(); let mut i 0; let mut res vec![]; while i s.len(){ let len s[i] as u8 as usize; i1; let j i len; if j s.len(){ let slice s[i..i len]; res.push(slice.into_iter().collect::String()); } ilen; } res }此外kotlin/0271-encode-and-decode-strings.kt 展示了逐字符编码思路把每个字符转成整数码点用|分隔字符、用/分隔字符串javascript/0271-encode-and-decode-strings.js 还给出了**分块传输编码Chunk Transfer Encoding**变体将长度写成固定 8 位的二进制串str.length.toString(2).padStart(8, 0)作为前缀解码时每 8 位解析一个长度。这些实现共同印证了「用长度做边界、无需转义内容」这一编码思想在不同约束下的普适性。6. 复杂度分析以方案二逐串length#string为例时间复杂度encode()对每个字符串做一次长度计算与拼接累计O(m n)其中n次是每个字符串前缀的固定开销decode()对每个字符串执行一次「扫描长度 截取内容」同样累计O(m n)且每个字符恰好被访问常数次。空间复杂度encode()需要存储结果字符串本身规模为O(m n)decode()需要存储还原出的n个字符串总规模同样为O(m n)。其中m为所有字符串长度之和n为字符串个数。这与 hints/string-encode-and-decode.md 给出的目标一致每次调用在线性时间内完成。7. 常见陷阱与边界条件articles/string-encode-and-decode.md 的「Common Pitfalls」小节归纳了三类高频出错点这里结合源码逐一说明。7.1 分隔符与内容冲突如果只用逗号、空格等常规字符做分隔一旦原始字符串包含该字符解码必然错位。长度前缀方案以「长度」为边界依据#只出现在「长度与内容之间」这一固定位置内容区即使包含#也不会影响解析——因为解码器读到#后立即按长度截取不会再去内容区里寻找分隔符。7.2 空列表与空字符串的区分encode([])与encode([])的编码结果不同encode([])→encode([])→0#长度0加分隔符内容区为空。因此解码时不能把「空串」一律当作空列表decode()应返回[]而decode(0#)应返回[]。方案一的 Python 实现与方案二均通过「编码串是否为空」这一前置判断来区分Swift 实现swift/0271-encode-and-decode-strings.swift则用#作为空列表哨兵同样保证了[]与[]不混淆。7.3 多位数长度的解析当字符串长度 ≥ 10 时长度前缀变为多位数如hello world是11#。解码时必须用循环读完整段数字直到#而不能假设长度只有一位。上述所有实现while s[j] ! #/while str[j] ! #/indexOf(#)等都正确处理了这一情况。7.4 其他边界空串元素[, a]编码为0##1#a解码时长度0正确还原空串含#的元素[a#b]编码为3#a#b解码先取3再截取a#b#不会造成歧义超长字符串若长度前缀采用定长字段如 Rust 的单字节变体需注意长度上限通用实现不受此限。8. 从提示到题解仓库文档的查阅路径如果你希望按「提示 → 完整题解 → 多语言源码」的顺序深入研究该题可以在当前仓库中按以下路径查阅资料类型仓库相对路径内容复杂度目标与三连提示hints/string-encode-and-decode.md目标复杂度、朴素分隔符思路的局限、长度前缀编码方案完整题解两种实现 陷阱articles/string-encode-and-decode.md两段式与逐串编码的算法步骤、11 种语言代码、复杂度与常见错误Python 实现python/0271-encode-and-decode-strings.py最优解逐串length#stringJava 实现java/0271-encode-and-decode-strings.java指针跨段写法C 实现cpp/0271-encode-and-decode-strings.cppto_string/stoi版本JavaScript 实现javascript/0271-encode-and-decode-strings.js朴素分隔符、非 ASCII 分隔符、二进制长度前缀等 4 种变体TypeScript 实现typescript/0271-encode-and-decode-strings.ts模板字符串一行式编码Go / Rust / Ruby / Swift / Kotlin / C#go/0271-encode-and-decode-strings.go 等分隔符变体|、单字节长度变体、两段式变体、逐字符编码变体9. 总结「字符串编解码」是一道典型的无歧义序列化设计问题。它的核心结论可以浓缩为一条可迁移到任何语言与场景的原则用「长度」而非「分隔符」来界定边界内容永远不需要转义。具体到本题最优方案对每个字符串输出length#string的成对序列解码时「读数字 → 跳过#→ 按长度取内容」循环往复即可在O(m)时间内完成一次编码或解码。这一思想广泛适用于网络协议中的消息分帧如 HTTP Chunked Transfer Encoding、日志管道中的批量消息打包、分布式系统中的数据持久化等真实场景——你在 javascript/0271-encode-and-decode-strings.js 中看到的二进制定长长度前缀变体正是这一思想的工程化体现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考