Encode and Decode Strings (LeetCode 271)

The problem

Design two functions. encode(strs) turns a list of strings into a single string. decode(s) turns that string back into the exact same list. The strings can contain any characters, including whatever you might want to use as a separator, and some may be empty.

Input:  ["lint", "code", "love", "you"]
Encoded: "4#lint4#code4#love3#you"
Decoded: ["lint", "code", "love", "you"]

The decoder must also round-trip awkward input like ["", "a#b", "12#x"].

How to think about it

Start with the obvious attempt. Join with a delimiter, say ",", and split on it. This breaks as soon as a string contains a comma. Escaping (\,) works but is fiddly: you must escape the escape character too, and decoding becomes a small state machine.

The key insight: say how long each string is before you write it. Write len(s), then a #, then the string itself. The decoder reads digits up to the first #, converts them to a number n, and then takes exactly n characters without looking at them. A # or a digit inside the content can’t confuse it, because the decoder never scans content for delimiters.

Why the # after the length is safe. The decoder only looks for # in places where a length is expected, and a length is made only of digits. So the first # it finds from the current position always ends the length.

Which pattern is this? Length-prefix framing, the way real network protocols split a byte stream into messages. The tell is “serialise arbitrary strings so they can be split again”.

Approach

1. Encode: for each string s, emit f"{len(s)}#{s}", and join them all.
2. Decode: start with i = 0 and an empty result list.
3. Find the next # at or after i; call it j. The length is int(s[i:j]).
4. The string is s[j + 1 : j + 1 + n]. Append it.
5. Move i to j + 1 + n and repeat until i reaches the end.

Solution

def encode(strs):
    return "".join(f"{len(s)}#{s}" for s in strs)     # length, '#', raw content
def decode(s):
    res, i = [], 0
    while i < len(s):
        j = s.index("#", i); n = int(s[i:j])         # read the length header
        res.append(s[j + 1:j + 1 + n]); i = j + 1 + n # take exactly n chars, unseen
    return res
# decode(encode(["lint", "code", "love", "you"])) -> ["lint", "code", "love", "you"]
# decode(encode(["", "a#b", "12#x"])) -> ["", "a#b", "12#x"]

Dry run

Decoding "4#lint4#code4#love3#you":

The awkward list encodes to "0#3#a#b4#12#x". The decoder reads 0, takes nothing, then reads 3 and takes a#b without being fooled by its #.

Complexity

• Time: O(L), where L is the total length of all strings. Each character is written once and read once. The length headers add O(k log L) digits for k strings.
• Space: O(L). For the encoded string and the decoded list.

Edge cases and pitfalls

• Empty list encodes to "" and decodes back to [].
• Empty strings encode as "0#" and come back as "", which a plain split would lose.
• Strings containing # or digits are safe, because content is skipped by length, never scanned.
• Splitting on the delimiter (s.split("#")) is the classic wrong answer. It fails on "a#b".
• Multi-digit lengths (10 or more characters) work because the decoder reads digits up to the #. A fixed one-digit header would break.

Related problems

• Serialize and Deserialize Binary Tree (LeetCode 297): the same encode/decode design question for a tree.
• Reverse Words in a String (LeetCode 151): where splitting on a delimiter is exactly right.
• Multiply Strings (LeetCode 43): another careful character-level string manipulation.