LeetCode 271 字符串编码与解码Encode and Decode Strings长度前缀编码实战与多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 271「字符串编码与解码」展开设计一种算法把字符串列表strs编码成单个字符串再将其无损解码回原列表。核心思路是长度前缀编码Length-Prefix Encoding——用长度信息精确标记每个字符串的边界从而彻底摆脱分隔符与内容冲突的问题。文中既给出两种经典实现长度列表 分隔符 两段式方案与逐串length#string最优方案的完整多语言代码也结合本仓库 python/0271-encode-and-decode-strings.py、cpp/0271-encode-and-decode-strings.cpp 等源码剖析其底层原理与工程化变体。读完你将掌握一种可应对任意字符内容含空串、逗号、#本身的通用序列化思路并能迁移到消息分帧、二进制协议、缓存序列化等真实场景。1. 前置知识在动手实现前建议先熟悉以下三点对应原文档 articles/string-encode-and-decode.md 的 Prerequisites 部分字符串操作能够按索引拼接、截取子串、定位字符这是编码与解码的基础分隔符设计理解选择不会与输入内容冲突的分隔符的难点以及为什么简单分隔符逗号、空格在内容不可控时并不可靠长度前缀编码利用字符串长度无歧义地标记编码段之间的边界这是本问题的核心思想。仓库配套的 hints/string-encode-and-decode.md 也从侧面印证了这一思路提示 1 指出朴素方案是使用非 ASCII 字符作分隔符提示 2 建议基于每个字符串的长度设计智能编解码提示 3 直接给出最终方案——先用一个数字表示字符串长度紧跟一个#分隔符再跟上字符串本身。2. 方案一长度列表 分隔符两段式编码2.1 直觉要把字符串列表编码成一个字符串关键在于解码时能正确切分。一个简单可靠的做法是先记录每个字符串的长度再接一个特殊分隔符最后把所有字符串内容顺序拼接。解码时根据记录的长度精确读取每个原始字符串应占用的字符数。由于是按长度切分字符串内部无论出现什么特殊字符、逗号或符号都不会影响边界的判断。2.2 编码算法若输入列表为空返回空字符串创建列表sizes逐个记录每个字符串的长度构建单个字符串把所有长度用逗号,连接追加#标记长度区段的结束按顺序追加所有字符串本体返回最终编码字符串。2.3 解码算法若编码字符串为空返回空列表从头读取字符直到遇到#解析出全部长度每个长度读到逗号为止越过#后按sizes逐个截取子串对每个长度sz读取sz个字符追加到结果返回解码后的字符串列表。2.4 多语言实现以下实现完整对应原文档方案一tabs 中的 Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust。Pythonclass 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 resJavapublic class Solution { public String encode(ListString strs) { if (strs.isEmpty()) return ; StringBuilder res new StringBuilder(); ListInteger sizes new ArrayList(); for (String str : strs) { sizes.add(str.length()); } for (int size : sizes) { res.append(size).append(,); } res.append(#); for (String str : strs) { res.append(str); } return res.toString(); } public ListString decode(String str) { if (str.length() 0) { return new ArrayList(); } ListString res new ArrayList(); ListInteger sizes new ArrayList(); int i 0; while (str.charAt(i) ! #) { StringBuilder cur new StringBuilder(); while (str.charAt(i) ! ,) { cur.append(str.charAt(i)); i; } sizes.add(Integer.parseInt(cur.toString())); i; } i; for (int sz : sizes) { res.add(str.substring(i, i sz)); i sz; } return res; } }Cclass Solution { public: string encode(vectorstring strs) { if (strs.empty()) return ; vectorint sizes; string res; for (string s : strs) { sizes.push_back(s.size()); } for (int sz : sizes) { res.append(to_string(sz)); res.push_back(,); } res.push_back(#); for (string s : strs) { res.append(s); } return res; } vectorstring decode(string s) { if (s.empty()) return {}; vectorint sizes; vectorstring res; int i 0; while (s[i] ! #) { int j i; while (s[j] ! ,) { j; } sizes.push_back(stoi(s.substr(i, j - i))); i j 1; } i; for (int sz : sizes) { res.push_back(s.substr(i, sz)); i sz; } return res; } };JavaScriptclass Solution { /** * param {string[]} strs * returns {string} */ encode(strs) { if (strs.length 0) return ; let sizes [], parts []; for (let s of strs) { sizes.push(s.length); } for (let sz of sizes) { parts.push(String(sz), ,); } parts.push(#, ...strs); return parts.join(); } /** * param {string} str * returns {string[]} */ decode(str) { if (str.length 0) return []; let sizes [], res [], i 0; while (str[i] ! #) { let j i; while (str[j] ! ,) { j; } sizes.push(parseInt(str.substring(i, j), 10)); i j 1; } i; for (let sz of sizes) { res.push(str.substr(i, sz)); i sz; } return res; } }C#public class Solution { public string Encode(IListstring strs) { if (strs.Count 0) return ; Listint sizes new Listint(); StringBuilder res new StringBuilder(); foreach (string s in strs) { sizes.Add(s.Length); } foreach (int sz in sizes) { res.Append(sz).Append(,); } res.Append(#); foreach (string s in strs) { res.Append(s); } return res.ToString(); } public Liststring Decode(string s) { if (s.Length 0) { return new Liststring(); } Listint sizes new Listint(); Liststring res new Liststring(); int i 0; while (s[i] ! #) { int j i; while (s[j] ! ,) { j; } sizes.Add(int.Parse(s.Substring(i, j - i))); i j 1; } i; foreach (int sz in sizes) { res.Add(s.Substring(i, sz)); i sz; } return res; } }Gotype Solution struct{} func (s *Solution) Encode(strs []string) string { if len(strs) 0 { return } var sizes []string for _, str : range strs { sizes append(sizes, strconv.Itoa(len(str))) } return strings.Join(sizes, ,) # strings.Join(strs, ) } func (s *Solution) Decode(encoded string) []string { if encoded { return []string{} } parts : strings.SplitN(encoded, #, 2) sizes : strings.Split(parts[0], ,) var res []string i : 0 for _, sz : range sizes { if sz { continue } length, _ : strconv.Atoi(sz) res append(res, parts[1][i:ilength]) i length } return res }Kotlinclass Solution { fun encode(strs: ListString): String { if (strs.isEmpty()) return val sizes mutableListOfString() for (str in strs) { sizes.add(str.length.toString()) } return sizes.joinToString(,) # strs.joinToString() } fun decode(encoded: String): ListString { if (encoded.isEmpty()) return emptyList() val parts encoded.split(#, limit 2) val sizes parts[0].split(,) val res mutableListOfString() var i 0 for (sz in sizes) { if (sz.isEmpty()) continue val length sz.toInt() res.add(parts[1].substring(i, i length)) i length } return res } }Swiftclass Solution { func encode(_ strs: [String]) - String { if strs.isEmpty { return } var sizes: [String] [] for s in strs { sizes.append(String(s.count)) } return sizes.joined(separator: ,) ,# strs.joined() } func decode(_ s: String) - [String] { if s.isEmpty { return [] } let sArr Array(s) var sizes: [Int] [] var res: [String] [] var i 0 while sArr[i] ! # { let start i while sArr[i] ! , { i 1 } sizes.append(Int(String(sArr[start..i]))!) i 1 } i 1 for sz in sizes { let substring String(sArr[i..isz]) res.append(substring) i sz } return res } }Rustimpl Solution { pub fn encode(strs: VecString) - String { if strs.is_empty() { return String::new(); } let mut res String::new(); let sizes: Vecusize strs.iter().map(|s| s.len()).collect(); for sz in sizes { res.push_str(sz.to_string()); res.push(,); } res.push(#); for s in strs { res.push_str(s); } res } pub fn decode(s: String) - VecString { if s.is_empty() { return vec![]; } let bytes s.as_bytes(); let mut sizes vec![]; let mut res vec![]; let mut i 0; while bytes[i] ! b# { let mut cur String::new(); while bytes[i] ! b, { cur.push(bytes[i] as char); i 1; } sizes.push(cur.parse::usize().unwrap()); i 1; } i 1; for sz in sizes { res.push(s[i..i sz].to_string()); i sz; } res } }2.5 复杂度分析时间复杂度每次encode()/decode()调用均为 $O(m n)$空间复杂度每次调用均为 $O(m n)$。其中 $m$ 是所有字符串的长度之和$n$ 是字符串的个数。3. 方案二逐串length#string最优方案3.1 直觉方案一需要先集中存长度、再集中存内容存在两段式开销。更优的做法是把每个字符串和它自己的长度紧挨着写对每个字符串写出长度#字符串。#作为长度与内容之间的明确边界而长度保证我们精确读取——无论字符串内部出现什么字符。解码时读到#得到长度再精确截取该长度个字符即为原始字符串。该方案结构更简单、更高效省去了单独维护长度区段的成本。3.2 编码算法初始化结果构建器或字符串片段列表遍历列表中的每个字符串计算其长度追加length#string返回最终编码字符串。3.3 解码算法初始化结果列表与指针i 0当i在编码字符串范围内时循环移动指针j直到遇到#——该区段即长度将s[i:j]转为整数length将i移到#之后截取接下来length个字符即原始字符串追加到结果列表将i前进length继续解码下一段返回解码后的字符串列表。3.4 多语言实现以下实现完整对应原文档方案二tabs 中的 Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust。Pythonclass Solution: def encode(self, strs: List[str]) - str: res [] for s in strs: res.append(str(len(s))) res.append(#) res.append(s) return .join(res) def decode(self, s: str) - List[str]: 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 resJavapublic class Solution { public String encode(ListString strs) { StringBuilder res new StringBuilder(); for (String s : strs) { res.append(s.length()).append(#).append(s); } return res.toString(); } public ListString decode(String str) { ListString res new ArrayList(); int i 0; while (i str.length()) { int j i; while (str.charAt(j) ! #) { j; } int length Integer.parseInt(str.substring(i, j)); i j 1; j i length; res.add(str.substring(i, j)); i j; } return res; } }Cclass Solution { public: string encode(vectorstring strs) { string res; for (const string s : strs) { res.append(to_string(s.size())); res.push_back(#); res.append(s); } return res; } vectorstring decode(string s) { vectorstring res; int i 0; while (i s.size()) { int j i; while (s[j] ! #) { j; } int length stoi(s.substr(i, j - i)); i j 1; j i length; res.push_back(s.substr(i, length)); i j; } return res; } };JavaScriptclass Solution { /** * param {string[]} strs * returns {string} */ encode(strs) { const res []; for (let s of strs) { res.push(String(s.length), #, s); } return res.join(); } /** * param {string} str * returns {string[]} */ decode(str) { let res []; let i 0; while (i str.length) { let j i; while (str[j] ! #) { j; } let length parseInt(str.substring(i, j)); i j 1; j i length; res.push(str.substring(i, j)); i j; } return res; } }C#public class Solution { public string Encode(IListstring strs) { StringBuilder res new StringBuilder(); foreach (string s in strs) { res.Append(s.Length).Append(#).Append(s); } return res.ToString(); } public Liststring Decode(string s) { Liststring res new Liststring(); int i 0; while (i s.Length) { int j i; while (s[j] ! #) { j; } int length int.Parse(s.Substring(i, j - i)); i j 1; j i length; res.Add(s.Substring(i, length)); i j; } return res; } }Gotype Solution struct{} func (s *Solution) Encode(strs []string) string { var res strings.Builder for _, str : range strs { res.WriteString(strconv.Itoa(len(str))) res.WriteByte(#) res.WriteString(str) } return res.String() } func (s *Solution) Decode(encoded string) []string { res : []string{} i : 0 for i len(encoded) { j : i for encoded[j] ! # { j } length, _ : strconv.Atoi(encoded[i:j]) i j 1 res append(res, encoded[i:ilength]) i length } return res }Kotlinclass Solution { fun encode(strs: ListString): String { val res StringBuilder() for (str in strs) { res.append(str.length).append(#).append(str) } return res.toString() } fun decode(encoded: String): ListString { val res mutableListOfString() var i 0 while (i encoded.length) { var j i while (encoded[j] ! #) { j } val length encoded.substring(i, j).toInt() i j 1 res.add(encoded.substring(i, i length)) i length } return res } }Swiftclass Solution { func encode(_ strs: [String]) - String { var res: [String] [] res.reserveCapacity(strs.count * 3) for s in strs { res.append(String(s.count)) res.append(#) res.append(s) } return res.joined() } func decode(_ s: String) - [String] { var res [String]() let sArr Array(s) var i 0 while i sArr.count { var j i while sArr[j] ! # { j 1 } let lengthStr String(sArr[i..j]) let length Int(lengthStr)! i j 1 let end i length let substring String(sArr[i..end]) res.append(substring) i end } return res } }Rustimpl Solution { pub fn encode(strs: VecString) - String { let mut res String::new(); for s in strs { res.push_str(s.len().to_string()); res.push(#); res.push_str(s); } res } pub fn decode(s: String) - VecString { let mut res vec![]; let bytes s.as_bytes(); let mut i 0; while i bytes.len() { let mut j i; while bytes[j] ! b# { j 1; } let length: usize s[i..j].parse().unwrap(); i j 1; j i length; res.push(s[i..j].to_string()); i j; } res } }3.5 复杂度分析时间复杂度每次encode()/decode()调用均为 $O(m n)$空间复杂度每次调用均为 $O(m n)$。其中 $m$ 是所有字符串的长度之和$n$ 是字符串的个数。两种方案复杂度相同但方案二在常数开销上更优无需先构建完整的长度区段再拼接内容同时解码逻辑也更直接——这正是本仓库多数语言实现选用的版本。4. 仓库源码中的实现细节与工程化变体4.1 与仓库实现的一致性印证python/0271-encode-and-decode-strings.py 采用方案二str(len(s)) # s解码时先扫到#取长度再按长度切分与上文 Python 最优实现完全一致java/0271-encode-and-decode-strings.java 用StringBuilder拼接str.length() # str解码用str.substring(j 1, i)一步到位cpp/0271-encode-and-decode-strings.cpp 以Codec类封装encode/decode注释中给出了典型调用方式Codec codec; codec.decode(codec.encode(strs));typescript/0271-encode-and-decode-strings.ts 用strs.map(str \${str.length}#${str}).join() 一行完成编码ruby/0271-encode-and-decode-strings.rb 同样采用#{str.length}##{str}逐串拼接swift/0271-encode-and-decode-strings.swift 是方案一的工程化版本counts.joined(separator: ,) # strs.joined()并额外处理了空串场景if strs.isEmpty { return # }解码端if s # { return [] }kotlin/0271-encode-and-decode-strings.kt 使用StringBuilder与encoded.split(#, limit 2)精确切分同时仓库中另有 kotlin/0217-encode-and-decode-strings.kt 保留另一版实现可对照阅读。4.2 变体一非 ASCII 字符作分隔符javascript/0271-encode-and-decode-strings.js 中给出了一种朴素但可行的变体取一个极不可能出现在输入中的非 ASCII 字符如String.fromCharCode(257)作为分隔符直接strs.join(nonASCIICode)编码、strs.split(nonASCIICode)解码。它的代价是只要某个字符串恰好包含该字符就会破坏解码。这与原文档 Common Pitfalls 中使用可能出现在字符串中的分隔符会破坏解码的警告遥相呼应——长度前缀方案正是为了彻底规避这一风险。4.3 变体二Chunk Transfer Encoding二进制长度前缀同一个 JS 文件中还演示了类似 HTTPTransfer-Encoding: chunked的分块传输编码思路先把字符串长度转成 8 位二进制str.length.toString(2).padStart(8, 0)再紧跟字符串本体。解码时先读固定 8 位得到二进制长度再截取对应字符。因为长度前缀是固定宽度的连分隔符都不需要了——这进一步印证了用长度而不是分隔符来定界这一核心思想的泛化能力。4.4 变体三单字节长度前缀与自定义分隔符rust/0271-encode-and-decode-strings.rs 把长度压缩为单个字节s.len() as u8 as char解码时取回len后按字符切片——空间更省但长度上限受限于单字节255适用于短字符串场景go/0271-encode-and-decode-strings.go 使用strings.Builder拼接并以|作为长度与内容的分隔符解码时手动将数字字符还原为整数(int(strs[j]) - 48) * dec展示了分隔符可自由替换、算法骨架不变的设计弹性。这些变体说明长度前缀编码是一个可定制骨架分隔符、长度宽度变长十进制 / 定长二进制 / 单字节、拼接方式StringBuilder/strings.Builder/ 数组 join都可以按需替换而先读长度、再按长度取内容的核心不变。5. 常见陷阱原文档在 articles/string-encode-and-decode.md 的 Common Pitfalls 一节总结了三个高频错误这里结合实现细节逐一展开5.1 使用了可能出现在字符串中的分隔符选用逗号、空格等简单分隔符一旦原始字符串内部出现该字符解码就会错位。长度前缀方案用长度精确指定读取字符数使内容本身变得无关紧要从根本上免疫该问题。仓库中非 ASCII 分隔符变体javascript/0271-encode-and-decode-strings.js正是这一陷阱的活教材。5.2 没有正确处理空字符串或空列表空输入列表与含一个空字符串的列表是两种不同的输入编码结果必须能区分输入方案一编码结果方案二编码结果[]空列表空串空串零次循环[]一个空串0#长度 0 #0#0# 空串[, a]0,1#a0#a解码端必须能正确还原长度为零的字符串方案二中length 0时s[i:i0]得到空串方案一的 Go 实现通过if sz { continue }跳过Split产生的空段Swift 实现则显式判断if sIndex endIndex { decodedStrings.append() }。对照 swift/0271-encode-and-decode-strings.swift 与 go/0271-encode-and-decode-strings.go 可看到两种边界处理风格。5.3 多位数长度的解析错误当字符串长度 ≥ 10 时长度前缀变为多位数。如果实现只假设单个数字解码就会截断。正确做法是用循环一直读到#分隔符为止把整段数字一次性解析成整数。上述所有实现如 Python 的while s[j] ! #: j 1C 的stoi(s.substr(i, j - i))都遵循这一原则。6. 总结维度方案一长度列表 分隔符方案二逐串length#string编码结构len1,len2,...#content...len1#s1len2#s2...解码方式先解析全部长度再统一切分边读长度边切分单趟完成时间复杂度$O(m n)$$O(m n)$空间复杂度$O(m n)$$O(m n)$常数开销较高两段式较低逐段内联空列表/空串处理需额外判断天然兼容核心要点用长度而不是分隔符来定界。长度前缀编码既能承载任意字符内容又天然兼容空字符串与多位数长度是字符串列表序列化的通用答案其思想还可推广到分块传输编码、二进制协议帧设计等场景。完整的 10 种语言实现可在仓库中按编号0271检索对照例如 python/0271-encode-and-decode-strings.py、cpp/0271-encode-and-decode-strings.cpp、javascript/0271-encode-and-decode-strings.js、rust/0271-encode-and-decode-strings.rs、go/0271-encode-and-decode-strings.go、typescript/0271-encode-and-decode-strings.ts、kotlin/0271-encode-and-decode-strings.kt、swift/0271-encode-and-decode-strings.swift、ruby/0271-encode-and-decode-strings.rb、csharp/0271-encode-and-decode-strings.cs 等。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考