NeetCode #99LC-271MediumArrays & HashingBlind 75NC 150NC 250NC Algo100
← Back to All Problems#99 · #271 · Encode and Decode Strings(字符串的编码与解码)
📌 Problem Statement & Constraints
Design an algorithm to encode a list of strings into a single string, and decode that string back into the original list. The input strings may contain any of the 256 valid ASCII characters, so no character can be reserved as a delimiter. Both
encode and decode are called on the same object.💡 Core Algorithmic Approaches
- Because any character may appear in the payload, a plain delimiter such as
,or#is unsafe -- it can occur inside a string. - Fix this with a length-prefixed format: for each string, emit
<length>#<content>and concatenate. - Decoding reads digits until it hits
#, which yields the exact number of following characters to consume. That removes all ambiguity, even if the payload itself contains#or digits. - The length prefix makes the format self-describing: the decoder never needs to guess where a string ends.
💻 Benchmark Python3 Implementation
class Codec:
def encode(self, strs: List[str]) -> str:
# Format: "<len>#<content>" repeated. The '#' after the digits is
# unambiguous because the length itself is pure digits.
return "".join(f"{len(s)}#{s}" for s in strs)
def decode(self, s: str) -> List[str]:
res = []
i = 0
while i < len(s):
j = i
while s[j] != "#": # scan the length prefix
j += 1
length = int(s[i:j])
start = j + 1
res.append(s[start:start + length])
i = start + length
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(N) for both directions, where N is the total number of characters across all strings.
💾 Space Complexity
O(N) for the encoded string (encode) and the decoded list (decode).
⚠️ Interview Pitfalls & Follow-ups
- Joining with a delimiter such as
',': breaks whenever a string contains that delimiter -- and the problem explicitly allows any ASCII character. - Writing
<len><content>without a separator: ambiguous, because"12"could mean length 1 followed by content starting with2, or length 12. The#(or any non-digit) terminates the length. - Parsing with
split('#'): fails when the payload contains#; you must consume exactlylengthcharacters after the prefix. - Using a JSON library: it works and is a legitimate answer to mention, but the point of the problem is to hand-roll the framing.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Arrays & Hashing Problems
中文速览与面试要点
字符串的编码与解码
请你设计一个算法,可以将一个字符串列表编码成一个字符串。这个编码后的字符串随后可以被解码成原始的字符串列表。要求:编码与解码必须是无损的,且解码结果必须与原始列表完全一致(包括空字符串与含特殊字符的字符串)。注意:本题为 LeetCode 会员题,同时也在 NeetCode 150 题单中。
核心要点
- 核心难点 :列表元素之间需要分隔符,但元素本身可能包含任意字符,因此 不能 用单个字符(如逗号、井号)作分隔符。
- 方案一 · 长度前缀(推荐) :对每个字符串编码为 len(s) + 分隔符 + s ,例如 ["neet","code"] → 4#neet4#code 。解码时先读到分隔符确定长度,再精确截取该长度的字符。
- 为什么长度前缀一定安全 :解码不依赖「猜分隔符」,而是用长度精确定位,因此元素内含任何字符(包括 #、逗号、换行、Unicode)都不会歧义。
- 方案二 · 转义 :定义转义字符,对元素中出现分隔符的位置做转义处理。可行但实现复杂,容易漏掉边界。
- 方案三 · 非 ASCII 分隔符 :用一个不可能出现在输入中的字符(如 chr(257))作分隔符。在 Python 中可行,但在只支持字节的语言里不可靠。
常见陷阱
- 用普通字符作分隔符 : ",".join(strs) 遇到元素本身含逗号就彻底失效。这是本题最经典的错误,务必在面试中主动指出并说明为何要用长度前缀。
- 解码时忘记处理空字符串 :空串编码为 0# ,长度字段为 0,截取为空串——本解天然正确,但若用「按分隔符 split」的思路,空串与空列表会混淆。
- s.index 的边界 :若输入格式非法(缺少 #), index 会抛 ValueError。生产代码应做校验,面试中说明「假设输入由本 encode 产生」即可。
- 多字节字符陷阱 :在按字节处理的场景(如 C++ 的 std::string)中,长度应取字节数而非字符数;Python 的 str 是 Unicode 码点序列, len 即字符数,两者需区分。
参考实现
class Solution:
def encode(self, strs: list[str]) -> str:
# 长度前缀:<长度>#<内容>
return ''.join(f'{len(s)}#{s}' for s in strs)
def decode(self, s: str) -> list[str]:
res, i = [], 0
while i < len(s):
j = s.index('#', i) # 定位长度字段的结束
length = int(s[i:j])
start = j + 1
res.append(s[start:start + length]) # 按长度精确截取
i = start + length
return res
# 方案三(Python 专用的极简写法,面试可作彩蛋):
# def encode(self, strs): return chr(257).join(strs)
# def decode(self, s): return s.split(chr(257)) if s else []