Encode and Decode Strings
Medium · Arrays & Hashing · Array · String · Design
Problem
Design a Codec that packs a list of strings into one string and unpacks it again:
- encode(strs) — return a single string
- decode(s) — rebuild the original list from that string
The list that comes back must equal the original exactly: the same number of strings, in the same order, with the same contents. The strings may contain any of the 256 ASCII characters — including whatever separator you are tempted to use — and may be empty. Do not lean on a serializer such as json or eval; the point is to design the format yourself.
The tests call encode on one Codec, hand the result to decode on a fresh Codec (as if on another machine), and compare the list that comes back with the one that went in.
Examples
Input: strs = ["Hello","World"] Output: ["Hello","World"]
One possible encoding is 5#Hello5#World; reading a length, then that many characters, recovers both words.
Input: strs = [""] Output: [""]
A list holding one empty string must come back as a list holding one empty string, not as an empty list.
Input: strs = ["#","##","5#abc"] Output: ["#","##","5#abc"]
The strings contain the separator and even look like encoded pieces; a length prefix still reads them back exactly.
Constraints
- 0 <= len(strs) <= 200
- 0 <= len(strs[i]) <= 200
- strs[i] may contain any of the 256 ASCII characters
Approaches
- Length prefix: len#string — time O(n), space O(n)
Follow-up
Could you design an encoding that works for arbitrary characters without escaping, and that tells an empty list apart from a list holding one empty string?
Related problems
Start free on Cariara · Coding problems · System design studio
