💬 Discord
Sign In
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.