Appearance
4.4.6 — Encode and Decode Strings
LeetCode 271 · Medium · ★ Blind 75
The problem
Write two functions. encode takes a list of strings and turns it into one single string. decode takes that single string and gives back the exact original list.
python
decode(encode(["lint", "code", "love", "you"]))
# must give back ["lint", "code", "love", "you"]There are up to 100 strings, each up to 200 characters long. Each string may contain any of the 256 ASCII characters. ASCII is the basic set of characters a computer uses for English text: letters, digits, punctuation, spaces and a few invisible control characters. That last rule is what makes the problem hard.
What the problem is really asking
Imagine you must send a list of messages to another computer, but the line between the two computers can only carry one long string. The other side has to cut that string back into the original messages, exactly.
So the real question is: how does the reader know where one message ends and the next begins? And it has to work even when the messages contain characters you might have wanted to use as a marker.
The brute force, and where it breaks
The first idea is to glue the strings together with a separator, and split on it later.
python
def encode(strs): return "#".join(strs)
def decode(s): return s.split("#")Try it on ["a#b", "c"].
- Encoding gives
"a#b#c". - Decoding splits on every
#and gives["a", "b", "c"].
Two strings went in and three came out. Nothing crashed, and no error was raised. The data is just quietly wrong.
This is called delimiter collision. A delimiter is a character that marks where one piece ends. A collision happens when the same character also appears inside the data. Choosing a rarer separator, like | or ~, does not fix it. The problem says every one of the 256 characters is allowed in the data. So no single character is safe as a separator.
The flaw in one sentence: a separator only works if the data can never contain it, and here the data can contain anything.
The idea
If you cannot mark where a string ends, say in advance how long it is.
Think about a moving truck. If the rule is "a red sticker means a new box starts here", the system breaks the moment someone packs a box full of red stickers. If instead every box has a label saying "this box holds exactly 5 items", the movers just count out 5 items. They never look at what the items are, so nothing inside can confuse them.
So we write each string as three parts: its length, then a # marker, then the string itself.
["lint", "code"] → "4#lint4#code"
["a#b", "c"] → "3#a#b1#c"To decode, the reader does two things over and over.
- Read digits until it reaches a
#. Those digits are the length. - Take exactly that many characters after the
#, whatever they are.
The figure below shows the reader working through "3#a#b1#c".
Read the figure from left to right. The amber boxes are lengths. The purple boxes are the # markers that end each length. The green boxes are the string contents. The reader reads 3, skips the purple #, and then takes exactly three green characters: a, #, b. The # in the middle is just treated as a normal character, because the reader was told "take 3" and simply took 3. Then it reads 1, skips the #, and takes c.
"If no character is safe, how is the # safe?" Interviewers ask this. The # is never used to separate the data. It only ends a run of digits, and the reader looks for it only while it is reading a length. A digit can never be #. And while the reader is taking string contents, it does not look for # at all. So the # is safe because of where the reader expects it, not because it is rare.
The solution
python
class Codec:
def encode(self, strs: List[str]) -> str:
return ''.join(f"{len(s)}#{s}" for s in strs) # (1)
def decode(self, s: str) -> List[str]:
result, i = [], 0 # (2)
while i < len(s): # (3)
j = i # (4)
while s[j] != '#': # (5)
j += 1
length = int(s[i:j]) # (6)
result.append(s[j + 1 : j + 1 + length]) # (7)
i = j + 1 + length # (8)
return resultts
function encode(strs: string[]): string {
return strs.map(s => `${s.length}#${s}`).join(''); // (1)
}
function decode(s: string): string[] {
const result: string[] = []; // (2)
let i = 0;
while (i < s.length) { // (3)
let j = i; // (4)
while (s[j] !== '#') j++; // (5)
const length = Number(s.slice(i, j)); // (6)
result.push(s.slice(j + 1, j + 1 + length)); // (7)
i = j + 1 + length; // (8)
}
return result;
}Line by line
(1) Encode. For each string s, build the piece f"{len(s)}#{s}". The f"..." form puts values inside a string: len(s) becomes the length as digits, then a #, then the string. For "lint" this gives "4#lint". Then ''.join(...) glues all the pieces together with nothing between them.
Why join and not a loop with result += piece? In Python a string can never be changed once made. So result += piece builds a brand new string and copies everything so far into it, every time. Over many pieces that copying adds up to roughly the square of the total length. join works out the final size first and copies each piece once.
(2) Start decoding. result will collect the strings. i is our position in the encoded string. It always points at the first digit of the next length. At the start that is position 0.
(3) Keep going until we reach the end. When i reaches the length of s, there is nothing left to read.
(4) Start a second pointer j at i. j is a scout. It will walk forward over the digits to find the #.
(5) Walk j until it stands on the #. Lengths can have more than one digit, like 12 or 200, so we cannot just read one character.
(6) Turn the digits into a number. s[i:j] takes the characters from position i up to but not including position j. Since j is on the #, this slice holds only the digits. int(...) turns the text "3" into the number 3.
(7) Take exactly length characters. The string starts one step after the #, at j + 1. It ends length characters later, at j + 1 + length. Python slices stop before the end position, so s[j + 1 : j + 1 + length] is exactly length characters long. We add it to result. Nothing inside it is examined.
(8) Jump to the next record. The next length starts right after the string we just took, at j + 1 + length.
The two "+ 1"s
Almost every bug in this problem lives in lines (7) and (8). Both need + 1 to step over the #.
- If you forget it in line (7), every decoded string starts with a
#and loses its last character. - If you forget it in line (8),
ilands on the last character of the string just read, not on the next digit. On the next turn,int(...)is handed non-digit text and crashes, or reads the wrong number.
A good habit is to say the rule out loud: "i always sits on the first digit of the next record." Then check that line (8) keeps that promise.
Trace
Decode s = "3#a#b1#c". The positions are: 0 3, 1 #, 2 a, 3 #, 4 b, 5 1, 6 #, 7 c.
| Round | i | j stops at | length | Slice taken | Next i |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 3 | s[2:5] = "a#b" | 2 + 3 = 5 |
| 2 | 5 | 6 | 1 | s[7:8] = "c" | 7 + 1 = 8 |
At round 3, i is 8, which equals the length of s, so the loop stops. The result is ["a#b", "c"]. The # at position 3 was never looked at by line (5), because j started at 5 in round 2.
Complexity, derived
Let N be the total number of characters across all the strings.
Encode time. We visit each string once to measure it, and join copies every character once. That is O(N). The length digits add a few characters per string, at most 3 here, so they do not change the order.
Decode time. Both pointers only ever move forward. j walks over the few digits of each length. The slice in line (7) copies each string's characters once. So every character of the encoded string is touched a fixed number of times, and decoding is O(N).
Space. The encoded string has about N characters, and the decoded list holds N characters. So O(N) both ways.
Edge cases
- An empty string in the list, such as
[""]. It encodes to"0#". Decoding reads the length 0 and takes a slice of zero characters, which is"". No special case is needed. Compare the separator idea:"#".join([""])is"", and so is"#".join([]). It cannot even tell "one empty string" from "no strings at all". When an edge case needs no extra code, that is usually a sign the design is right. - An empty list. It encodes to
"". The decode loop never runs and returns[]. - A string made of digits, such as
["123"]. It encodes to"3#123". The reader stops at the first#, gets 3, and then takes"123"without treating those digits as a length. - A string full of
#s, such as["###"]. It encodes to"3####". The reader takes 3 characters after the first#, which are"###".
The other real answer — escaping
There is a second correct design. Pick a separator, and whenever that character appears inside the data, write it in a special way so the reader can tell the difference. This is called escaping. For example, you could write a real : inside the data as ::, and use :; to mean "end of string".
You have met escaping before without the name. A spreadsheet saved as CSV puts quotes around a cell that contains a comma. A command line uses a backslash before a space inside a file name.
Length prefixing is better when you know each string's length before you start writing it, which we do here. Its reader never has to look inside the data at all. Escaping is better when the data arrives a little at a time and you cannot know its length in advance.
Variations you will meet
This is not just a puzzle. Real systems send data exactly this way.
- Web pages. When a server sends a page, it first writes a header line such as
Content-Length: 4096, then exactly 4,096 bytes of data. The data can contain anything. Chapter 5.6 covers what happens when that length is wrong. - Network connections. The basic connection under the web, called TCP, delivers a stream of bytes with no boundaries at all. So every program that talks over it must frame its own messages, usually with a length prefix.
- Databases store a text column of varying length as "a few bytes saying how long, then the text".
The general lesson: when the data can contain anything, describe its length up front instead of marking its end.
What the interviewer will push on
"Why not just join with a comma?" They are checking that you see the collision. The data can contain a comma. No character is safe as a separator.
"Then why is your # safe?" They want the answer about position. The reader only looks for # right after a length, and it never looks inside the string contents.
"How would you handle very long strings that arrive in pieces?" You may not know the full length up front. Send the string in chunks: write a chunk's length, then that chunk, and repeat. Finish with a length of zero. The web uses exactly this, under the name chunked transfer encoding.
"What if someone sends you a corrupted string?" A wrong length can make the reader run past the end. A real reader checks that j stays inside the string in line (5), and that j + 1 + length is not past the end in line (7). On a judge these checks are not needed. In a network program, leaving them out lets an attacker crash your server.
One thing to volunteer: point out that the empty string needs no special case in this design, while a separator design cannot even tell [""] from [].
Next: 4.4.7 Product of Array Except Self. No hashing at all, and a different way to remove a nested loop.