Encode and Decode Strings

The problem

Write two functions. encode takes a list of strings and turns it into one string. decode takes that one string and gives back the original list, exactly as it was.

The strings can hold any ASCII character, including spaces, digits, # and every other symbol. A string can also be empty. decode(encode(words)) must always equal words.

Example 1

Input: words = ["hi", "a#b", ""]

Output: ["hi", "a#b", ""]

One valid encoding is “2#hi3#a#b0#”. Decoding it gives back all three words, the empty one too.

words

"hi"0"a#b"1""2

encoded

20#1h2i334#5a6#7b809#10

Example 2

Input: words = ["4#x"]

Output: ["4#x"]

The word itself looks like a length prefix. It is encoded as “3#4#x”, and the decoder still reads it correctly.

Example 3

Input: words = []

Output: []

An empty list encodes to the empty string, and that decodes back to an empty list.

Constraints

• 0 ≤ number of strings ≤ 200
• 0 ≤ words[i].length ≤ 200
• words[i] holds any of the 256 ASCII characters.
• Below, L is the total length of all the strings.

Clarifying questions

Can a string contain the separator I pick?

Yes. Any character can appear, so no separator is safe on its own.

Can a string be empty?

Yes, and the list can be empty too. Both must come back exactly.

Does the encoded string need a fixed format?

No. Any format works, as long as your decode reads what your encode wrote.

May decode keep state from encode?

No. Decode must work from the string alone, as if it ran on another machine.

Spot the pattern

Joining words with a separator fails as soon as a word contains that separator. The fix is to stop looking for the end of a word and say in advance how long it is. This is how many network protocols frame messages: a length, then exactly that many bytes.

Solutions

Length prefixO(L)

Show all

This problem has one approach worth showing. Joining with a plain separator is broken, and escaping special characters works but is longer and easy to get wrong.

Length prefix O(L)

The idea

Encode: for each word, write its length, then a #, then the word. So “hi” becomes “2#hi” and “a#b” becomes “3#a#b”.

Decode: start at position i = 0. Read digits up to the next #. Those digits are the length size. The word is then exactly the next size characters, whatever they are. Take them, jump i past them, and repeat until the end.

The # only has to mark where the digits end, and digits never contain a #. Inside a word, a # is never searched for, because the decoder jumps over the word by its length.

Why it is correct: at every step, i points at the start of a length. The length tells the decoder exactly where the word ends, so the next i is again the start of a length.

Walkthrough

words

"hi"0"a#b"1""2

encoded

""

1. def encode(words):
2. encoded = ""
3. for word in words:
4. encoded += str(len(word)) + "#" + word
5. return encoded
6. def decode(encoded):
7. words, i = [], 0
8. while i < len(encoded):
9. hash_index = encoded.index("#", i)
10. size = int(encoded[i:hash_index])
11. words.append(encoded[hash_index + 1 : hash_index + 1 + size])
12. i = hash_index + 1 + size
13. return words

Encode: write each word as its length, a #, then the word itself. Start with an empty string.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Length prefix: write each word as "<length>#<word>".
// Every character is written once and read once, so O(L) time and memory,
// where L is the total length of all words.
class Codec {
    public String encode(List<String> words) {
        // A StringBuilder keeps building the string linear.
        StringBuilder encoded = new StringBuilder();
        for (String word : words) encoded.append(word.length()).append('#').append(word);
        return encoded.toString();
    }

    public List<String> decode(String encoded) {
        List<String> words = new ArrayList<>();
        int i = 0;
        while (i < encoded.length()) {
            // The first # after i always ends the length: digits never contain #.
            int hashIndex = encoded.indexOf('#', i);
            int size = Integer.parseInt(encoded.substring(i, hashIndex));
            // Take exactly size characters, so a # inside the word is harmless.
            words.add(encoded.substring(hashIndex + 1, hashIndex + 1 + size));
            i = hashIndex + 1 + size;
        }
        return words;
    }
}

Big O

Time O(L)Space O(L)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   In encode, each run of the loop writes one word with its prefix. In decode, each run of the loop reads one prefix and copies one word. The work in one run is not 1 step: it is the length of that word plus its few prefix characters. So count characters, not runs.

   1. def encode(words):
   2. encoded = ""
   3. for word in words:
   4. encoded += str(len(word)) + "#" + word
   5. return encoded
   6. def decode(encoded):
   7. words, i = [], 0
   8. while i < len(encoded):
   9. hash_index = encoded.index("#", i)
   10. size = int(encoded[i:hash_index])
   11. words.append(encoded[hash_index + 1 : hash_index + 1 + size])
   12. i = hash_index + 1 + size
   13. return words

2. 2 Count the runs on Example 1

   The encoded string in Example 1 is “2#hi3#a#b0#”. decode reads 4 characters for “2#hi”, 5 for “3#a#b” and 2 for “0#”.

   4 + 5 + 2 = 11 characters, each read once. That is the whole string, no more.

   word	letters	prefix	characters read
   "hi"	2	2#	4
   "a#b"	3	3#	5
   ""	0	0#	2

   total

   4 + 5 + 2 = 11 = len(encoded)

3. 3 Write the count for any n

   For each word, the work is its length plus its prefix: a few digits (at most 3, since a word has at most 200 characters) and one #. With w words of total length L:

   L + w × (digits + 1) ≤ L + 4w

   Check it with Example 1: 5 letters + 3 words × 2 = 11.

4. 4 Keep only the part that grows fastest

   • Drop the 4w. Each word adds at most 4 characters of prefix, a fixed amount per word. When the words get longer, L takes over.

   What is left is L. encode is the same count, since it writes what decode reads.

   So the time is O(L).

5. S Space: count the extra memory the same way

   encode builds one string of about L characters. decode builds a list that holds all L characters again. The space is O(L), which the output needs anyway. i, hash_index and size are a fixed few numbers.

   encoded (L characters)words (L characters)ihash_indexsize

Common mistake

Adding to a string in a loop

In Java, C# and Go, encoded = encoded + piece copies the whole string so far on every step. With many words that turns O(L) into O(L²). Use a StringBuilder, a strings.Builder or a list of pieces joined once at the end.

Tested at the limits

2,000 random lists of 0 to 5 words, mostly made of # and digits, so words like 3# and 12#ab that look like a length prefix come up often. Empty lists and empty words too. Decoding the encoded text gave back the exact same words every time.

Largest inputs	Result
200 words of up to 200 characters (the most allowed), any ASCII character, plus one word that is 9# repeated 100 times. Length prefix.	Under 0.001 s, and about 0.05 MB of extra memory: the encoded text and the decoded words, a few copies of L.