⚡Flashcard Drill➔
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

  1. Because any character may appear in the payload, a plain delimiter such as , or # is unsafe -- it can occur inside a string.
  2. Fix this with a length-prefixed format: for each string, emit <length>#<content> and concatenate.
  3. 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.
  4. 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 with 2, or length 12. The # (or any non-digit) terminates the length.
  • Parsing with split('#'): fails when the payload contains #; you must consume exactly length characters 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.
🎯 Drill This Card Now➔

🧩 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 []