# Encode and Decode Strings

[link](https://leetcode.com/problems/encode-and-decode-strings/) · Medium · `string`, `design`, `length prefix`

> to pack variable-length items that can contain anything into one string or byte stream, use length-prefix framing: write the length, then the data, and have the reader jump by the length instead of searching for a separator. (HTTP Content-Length, Redis RESP and protobuf all work this way.) A separator alone only works if you also escape it.

## Problem

> Design an algorithm to encode a list of strings to a string. The encoded string is then sent
> over the network and is decoded back to the original list of strings.
> Implement `encode(strs) -> str` (Machine 1, sender) and `decode(s) -> list[str]`
> (Machine 2, receiver) so that `decode(encode(strs)) == strs`.

**Example 1**
```
Input:  strs = ["Hello", "World"]
Output: ["Hello", "World"]
```

**Example 2**
```
Input:  strs = [""]
Output: [""]
```

**Constraints**
- `0 <= len(strs) < 100`
- `0 <= len(strs[i]) < 200`
- `strs[i]` contains any possible characters out of 256 valid ASCII characters.

## Thinking

Let $N$ = total number of characters in all strings, $m$ = `len(strs)`.

- **Naive idea (wrong):** join with a separator, `"#".join(strs)`, and `split("#")`. It breaks
  as soon as a word contains the separator (`["a#b"]` → `"a#b"` → `["a", "b"]`), and the problem
  allows **any** character, so no separator is safe on its own. It also can't tell `[]` from `[""]`.
- **Key insight:** don't look *inside* the words at all. Write each word's **length** in front of
  it: `"5#Hello5#World"`. The decoder reads the length, then **jumps** over exactly that many
  characters, so it never matters what they are.
  - The `#` only marks where the length's digits end (lengths can have up to 3 digits).
  - The first `#` after a header's start is always the real separator, because the header is
    only digits.
- **The decoder needs an index it controls** (`while i < len(s)`), not a `for` loop, because it
  must jump a variable distance.
- **Edge cases to remember:** `[]` (encodes to `""`), `[""]` (encodes to `"0#"`), words that
  contain `#` or digits (`"1#a"`, `"5#"`), multi-digit lengths (≥ 10 chars), any ASCII character
  including `\x00`.

## Solution

### Approach A — my version (length + `#` prefix)

**Complexity:** Time $O(N)$ · Space $O(N)$. Correct, and the same algorithm as the best practice.
- `encode` is fine.
- In `decode`, `s.find("#", i)` only scans the few header digits, and `i` jumps over the word,
  so every character is visited about once.
- `if len(s) == 1: return output` is dead code: no input encodes to a 1-character string
  (`[]` → `""`, `[""]` → `"0#"`, `["a"]` → `"1#a"`). It was a patch for an earlier bug.

Unchanged except for the signatures; the commented-out first attempt is left out.

```python
def encode_mine(strs: list[str]) -> str:
    output_list = []
    for word in strs:
        output_list.append(str(len(word)) + "#" + word)
    return "".join(output_list)

def decode_mine(s: str) -> list[str]:
    output = []
    if len(s) == 1:  # dead code: no encoded string has length 1
        return output
    i = 0
    while i < len(s):
        deli = s.find("#", i)
        length = int(s[i:deli])
        output.append(s[deli + 1: deli + 1 + length])
        i = deli + length + 1
    return output
```

### Approach B — length + delimiter prefix ✅ best practice

**Complexity:** Time $O(N)$ · Space $O(N)$.
My version without the special case, with clearer names: `start` is where the word begins, and
the next header begins right after the word ends.

```python
def encode(strs: list[str]) -> str:
    return "".join(f"{len(word)}#{word}" for word in strs)

def decode(s: str) -> list[str]:
    result = []
    i = 0                          # always points at the start of a header
    while i < len(s):
        j = s.find("#", i)         # end of the length digits
        start = j + 1
        end = start + int(s[i:j])
        result.append(s[start:end])
        i = end                    # jump over the word: never read its contents
    return result
```

### Approach C — fixed-width length header (no delimiter)

**Complexity:** Time $O(N)$ · Space $O(N)$.
If every length is written with the same number of digits, the decoder doesn't need a `#`: it
always reads exactly 3 characters. Lengths are `< 200`, so 3 digits always fit. Real network
protocols use this idea with a fixed-size binary length (e.g. 4 bytes). The catch: you must know
the maximum length in advance; Approach B works for any length.

```python
WIDTH = 3  # len(word) < 200 fits in 3 digits

def encode_fixed(strs: list[str]) -> str:
    return "".join(f"{len(word):0{WIDTH}d}{word}" for word in strs)  # 5 -> "005"

def decode_fixed(s: str) -> list[str]:
    result = []
    i = 0
    while i < len(s):
        start = i + WIDTH
        end = start + int(s[i:start])
        result.append(s[start:end])
        i = end
    return result
```

## Scratch / Experiments

Max size: 99 random strings of 199 characters drawn from all 256 ASCII codes. All three are $O(N)$.
A and B are about the same (~33 µs). C is ~30% slower here; the likely cost is the nested format
spec `{len(word):0{WIDTH}d}`, which is more work per word than `{len(word)}`. The whole round
trip is tens of microseconds, so choose by correctness and simplicity, not speed.

```python
import random

random.seed(0)
strs = ["".join(chr(random.randrange(256)) for _ in range(199)) for _ in range(99)]

for enc, dec in PAIRS:
    print(enc.__name__, "+", dec.__name__)
    %timeit dec(enc(strs))
```

## Takeaways

- **Pattern:** to pack variable-length items that can contain *anything* into one string or
  byte stream, use **length-prefix framing**: write the length, then the data, and have the reader
  **jump** by the length instead of searching for a separator. (HTTP `Content-Length`, Redis
  RESP and protobuf all work this way.) A separator alone only works if you also escape it.
- **Mistakes I made:**
  - `char.isnumeric` without `()`: that's the method object, which is always truthy.
    Methods need `()` to run.
  - Read the length as a single character: lengths can have several digits. Read up to the `#`.
  - Scanned every character with `for … enumerate(s)`: the loop stopped at `#`s inside words.
    **You can't change a `for` loop's index**; assigning to it is overwritten on the next
    iteration. To jump, use `while` with your own index.
  - `enumerate(s[i:])` numbers the slice from 0, not from `i`, so the indexes were off by `i`.
    `s.find("#", i)` searches from `i` and returns an index in `s`.
  - Added `if len(s) == 1` to patch a symptom: no encoded string has length 1. Fix the cause
    rather than special-casing one input.
- **Related problems:** Serialize and Deserialize Binary Tree (#297, same encode/decode design
  for a tree), String Compression (#443, writing counts into a string), Decode String (#394,
  parsing a number followed by content), Count and Say (#38, reading runs of digits).

---

From https://taosu.blog/notes/0271-encode-and-decode-strings