Encode and Decode Strings

The problem

Write two functions. encode takes a list of strings and returns one string. decode takes that one string and returns the original list exactly. The list may be empty, and the strings may be empty and may contain any characters at all. decode gets only the encoded string: it cannot use anything encode remembered.

What to write

Implement the named encoder and decoder functions. The judge calls them separately and verifies the round trip.

Input
strs = ["hello","world"]

Output
["hello","world"]

Input
strs = ["","#","12#abc","🙂"]

Output
["","#","12#abc","🙂"]

Constraints

Inputs may contain empty strings, delimiters, and Unicode; 0 ≤ strs.length ≤ 200 and each string has at most 200 characters.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The strings can contain any character at all, including whatever you choose as a separator. So joining them with a comma, a "#" or any other mark cannot work by itself.

2. Hint 2: Ask a smaller question

   Picture the decoder reading your text one character at a time. What would it need to be told before a string begins, so that no character inside the string can fool it?

3. Hint 3: Name the pattern

   Write each string's length in front of it, then a marker to end the number, then the string. The decoder reads a length and takes that many characters without looking at them. This is length-prefixed encoding. Read the lesson on length-prefixed encoding.

4. Hint 4: State the invariant

   The decoder always stands at the start of a length. The number runs up to the first "#" after that point. The characters after the "#", as many as the number says, are one whole string, whatever they contain.

5. Hint 5: Sketch the pseudocode

   Encode: for each string write its length, then "#", then the string. Decode: start at position 0; while text remains, find the next "#", read the number before it, take that many characters after it, and jump past them.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Prefix every string with its length and a separator. To decode, read the length, then take exactly that many characters.

The slow way

Join the strings with a separator such as a comma and split on it to decode. It breaks as soon as a string contains the separator, and it cannot tell an empty list from a list holding one empty string.

The insight

A separator fails because the decoder has to search the text for it. If each string comes with its length in front, the decoder never searches inside a string: it counts characters, so the contents cannot confuse it.

Step by step

1. Write each string as its length, a "#", then the string itself. The length tells the decoder how far to read. The "#" only ends the number, so that a length of 12 followed by a string starting with 3 is not read as 123.
2. Decode from the start of the text until none is left. The encoded text is one string after another with nothing in between, so the decoder reads one string per round and stops when the position reaches the end.
3. Read the digits up to the next "#": that is the length. The decoder is at the start of a length, which is made of digits only. So the first "#" from here always ends the number, even if the string itself contains more of them.
4. Take exactly that many characters after the "#". The characters are counted, not inspected, so a "#" or a digit inside the string is copied like any other character.
5. Continue right after the string that was read. The next length starts immediately after the last character of this string, so the decoder is again at the start of a length.

The same numbered steps are the comments in each solution.

function encode(strs) {
  // 1. Write each string as its length, a "#", then the string itself
  return strs.map((s) => s.length + "#" + s).join("");
}
function decode(data) {
  // 2. Decode from the start of the text until none is left
  const out = [];
  let i = 0;
  while (i < data.length) {
    // 3. Read the digits up to the next "#": that is the length
    const end = data.indexOf("#", i),
      length = Number(data.slice(i, end));
    // 4. Take exactly that many characters after the "#"
    out.push(data.slice(end + 1, end + 1 + length));
    // 5. Continue right after the string that was read
    i = end + 1 + length;
  }
  return out;
}

function encode(strs: string[]): string {
  // 1. Write each string as its length, a "#", then the string itself
  return strs.map((s) => s.length + "#" + s).join("");
}
function decode(data: string): string[] {
  // 2. Decode from the start of the text until none is left
  const out: string[] = [];
  let i = 0;
  while (i < data.length) {
    // 3. Read the digits up to the next "#": that is the length
    const end = data.indexOf("#", i),
      length = Number(data.slice(i, end));
    // 4. Take exactly that many characters after the "#"
    out.push(data.slice(end + 1, end + 1 + length));
    // 5. Continue right after the string that was read
    i = end + 1 + length;
  }
  return out;
}

def encode(strs):
    # 1. Write each string as its length, a "#", then the string itself
    return "".join(f"{len(s)}#{s}" for s in strs)


def decode(data):
    # 2. Decode from the start of the text until none is left
    out = []
    i = 0
    while i < len(data):
        # 3. Read the digits up to the next "#": that is the length
        end = data.index("#", i)
        length = int(data[i:end])
        # 4. Take exactly that many characters after the "#"
        out.append(data[end + 1 : end + 1 + length])
        # 5. Continue right after the string that was read
        i = end + 1 + length
    return out

Example 1, traced

Input
strs = ["hello","world"]

Output
["hello","world"]

Why it works

The decoder is always at the start of a length. It reads digits up to the first "#", which the encoder wrote, then takes exactly as many characters as the encoder wrote for that string. So it lands where the encoder started the next one, and the lists match item by item.

Time and space

Time O(total characters), extra space O(total characters). Encoding and decoding each handle every character once, plus a few characters of length for each string, so the time grows with the total number of characters. The encoded text and the decoded list are about that size too.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Look for the "#" starting from the current position, not from the beginning of the text. From the beginning, the search finds the first string's marker again for every later string.
• Do not drop the marker after the length. Without it, the string "34" written after its length 2 reads as the number 234.
• An empty string still has to be written, as "0#". Skipping it changes the number of strings that come back.

Pattern

Length-prefixed encoding.

Keep going