Problem 65 · Strings & Tries

Encode and Decode List of Strings

MediumClassic DSA & systems

01Problem

Design encode(list[str]) -> str and decode(str) -> list[str] such that decode(encode(x)) == x for any strings, including empty strings and strings containing any delimiter.

02Key insight

Length-prefix framing (len + ':' + payload) is unambiguous for arbitrary content, unlike delimiter escaping; this is the same idea as wire protocols (Redis RESP, protobuf length-delimited).

03Solution

solution.pypython14 lines

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


def decode(data: str) -> list[str]:
    out: list[str] = []
    i = 0
    while i < len(data):
        colon = data.index(":", i)
        length = int(data[i:colon])
        start = colon + 1
        out.append(data[start:start + length])
        i = start + length
    return out

Try it first.

TimeO(total length)

SpaceO(total length)

tests.py · 2 passing

tests.pypython3 lines

for case in [[], [""], ["a", "", "b"], ["12:ab", "::", "#$%"], ["héllo", "世界"]]:
    assert decode(encode(case)) == case
assert encode(["ab"]) == "2:ab"

04Staff-level follow-up

For binary transport across languages? Use fixed-width big-endian byte lengths (or varints) over UTF-8 bytes, not char counts, so decoders never depend on string encoding.