LeetCode 271 · Arrays & Hashing

Encode and Decode Strings, explained with a picture

Parcels on a conveyor, each with a length label.

MediumArrays & Hashing
▶ Watch it step by step

The problem

Design two functions: encode turns a list of words into one single string, and decode turns that string back into exactly the same list. The words may contain any character, including # or :.

Input:  ["we", "say", ":", "yes"]
Encoded: "2#we3#say1#:3#yes"
Decoded: ["we", "say", ":", "yes"]

Picture it

Picture a single conveyor belt carrying parcels. If we just glued words together, we would not know where one ends. So each parcel gets a length label stuck on the front, like “3#”. The receiver reads the number, skips the #, and then takes exactly that many characters, whatever they are. Because it counts characters instead of hunting for a separator, a word containing # or : can’t confuse it.

How to recognise it

  • You must pack many strings into one and unpack them again exactly.
  • The strings may contain any character, so no separator character is safe on its own.
  • The receiver reads left to right and must know where each piece ends before reading it.
  • This is the same problem as framing messages on a network stream: the standard fix is to send the length first.

Start with brute force

The obvious attempt is to join the words with a separator and split on it again.

def encode_naive(words):
    return "#".join(words)

def decode_naive(tape):
    return tape.split("#")

Speed is not the problem here: both functions are O(L), where L is the total number of characters. Correctness is. LeetCode allows up to 200 words of up to 200 characters, each drawn from all 256 ASCII characters, so # can be inside a word. ["a#b", "c"] encodes to "a#b#c" and decodes to ["a", "b", "c"]. Even [] and [""] both encode to "", so the decoder cannot tell them apart.

Escaping (writing # inside words as some special sequence) can be made to work, but it is fiddly and easy to get wrong.

From brute force to the idea

  1. Find the flaw. A separator fails because the decoder must guess whether each # is data or a boundary.
  2. Say how long each piece is. If the decoder knows a word has n characters, it can copy exactly n characters without looking at what they are. A # inside the word is then just data.
  3. Mark where the number ends. Lengths have different numbers of digits, so put one # after each length. The decoder reads digits up to the first # it meets.
  4. That # is always the right one. The decoder starts at a length, and a length contains only digits. So the first # after position i ends the length, never a word.
  5. Jump past the word. After copying n characters, the next length starts right there, at j + 1 + n.

This is the key idea: length-prefix framing, written as length#word, so the content is never scanned for separators.

The key idea

Prefix each word with its length and a marker. Decoding reads the length first, so any character is safe inside the words.

Python solution

def encode(words):
    return "".join(f"{len(w)}#{w}" for w in words)

def decode(tape):
    out, i = [], 0
    while i < len(tape):
        j = tape.index("#", i)      # length ends at the first #
        n = int(tape[i:j])
        out.append(tape[j + 1:j + 1 + n])
        i = j + 1 + n
    return out

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Separator join (naive)O(L): one join and one split, but it decodes some inputs wronglyO(L): the joined string
Length prefix (shown code)O(L): tape.index only scans the digits of each length, and each word is copied onceO(L): the tape and the output

Here L is the total length of all words plus their headers.

Edge cases

  • Empty list: encode([]) is "", and decode("") returns [].
  • One empty word: encode([""]) is "0#", which decodes to [""]. Unlike the naive version, [] and [""] stay different.
  • Words that look like headers: ["3#a", "12#"] encodes to "3#3#a3#12#" and decodes correctly, because the decoder never reads inside a word.
  • Long words: a length of 15 is written as "15#"; multi-digit lengths are read by int(tape[i:j]).
  • Non-ASCII text: works in Python because len and slicing both count characters. If you encode to bytes, the lengths must count bytes instead.
  • Corrupt input: if the tape is cut short, index raises ValueError or the last word comes back shorter. The shown code assumes the tape came from encode.

Common mistakes

  • Searching for the # from the start of the tape (tape.index("#")) instead of from position i. It keeps finding the first header's #, so from the second word on the length slice is wrong: for ["ab", "cd"] it is empty and int raises ValueError.
  • Moving i to j + n instead of j + 1 + n, which forgets to skip the # itself.
  • Reading only one digit for the length, which breaks for words of 10 or more characters.
Your turn: fixed-width headers

Network protocols often avoid the # entirely by writing every length with a fixed number of digits. Write encode and decode that use a 4-digit length (so a word of length 2 starts with "0002"), assuming no word is longer than 9,999 characters. Describe your approach, then write it if you like.

Compare with our answer

With a fixed width, the decoder always knows the header is exactly the next 4 characters, so there is nothing to search for.

def encode_fixed(words):
    return "".join(f"{len(w):04d}{w}" for w in words)

def decode_fixed(tape):
    out, i = [], 0
    while i < len(tape):
        n = int(tape[i:i + 4])
        out.append(tape[i + 4:i + 4 + n])
        i += 4 + n
    return out

encode_fixed(["hi", ""]) is "0002hi0000". Time O(L), space O(L). The trade-off: every header costs 4 characters even for short words, and words longer than 9,999 characters cannot be encoded.

A strong answer mentions: why no separator is needed, the :04d zero-padding, and the maximum length the fixed width imposes.

Check what stuck

1. Your service sends many binary messages, one after another, over a single TCP connection. How should the receiver tell where each message ends?

2. Why does tape.index("#", i) in the shown decoder never stop at a # inside a word?

3. What does the shown encode([""]) return, and what does decode turn it back into?

Score 60% or more and the lesson is marked complete.