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
- Find the flaw. A separator fails because the decoder must guess whether each
#is data or a boundary. - 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. - 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. - 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. - 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 outIn 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
| Approach | Time | Space |
|---|---|---|
| Separator join (naive) | O(L): one join and one split, but it decodes some inputs wrongly | O(L): the joined string |
| Length prefix (shown code) | O(L): tape.index only scans the digits of each length, and each word is copied once | O(L): the tape and the output |
Here L is the total length of all words plus their headers.
Edge cases
- Empty list:
encode([])is"", anddecode("")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 byint(tape[i:j]). - Non-ASCII text: works in Python because
lenand slicing both count characters. If you encode to bytes, the lengths must count bytes instead. - Corrupt input: if the tape is cut short,
indexraisesValueErroror the last word comes back shorter. The shown code assumes the tape came fromencode.
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 andintraisesValueError. - Moving i to
j + ninstead ofj + 1 + n, which forgets to skip the#itself. - Reading only one digit for the length, which breaks for words of 10 or more characters.
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.
1. Your service sends many binary messages, one after another, over a single TCP connection. How should the receiver tell where each message ends?
Binary data may contain any byte, including newlines and quotes, so only a length prefix is safe. TCP is a byte stream and does not keep your packet boundaries, so the receiver may see several messages joined together.
2. Why does tape.index("#", i) in the shown decoder never stop at a # inside a word?
The loop only ever sets i to the start of a header. Headers are digits followed by #, so the first # after i ends the header. The word after it is then copied by length, never searched.
3. What does the shown encode([""]) return, and what does decode turn it back into?
An empty word still gets a header with length 0. The decoder reads 0, copies an empty slice, and moves past the #. That is why [] (encoded as "") and [""] stay distinguishable.
Score 60% or more and the lesson is marked complete.