DSA · Design · #66
Encode and Decode Strings
Module 57 · difficulty 3/5·⏱ 30:00starts on first keystroke
Design an algorithm to encode a **list of strings** into a single string. The encoded string is then sent over the network and is decoded back to the original list of strings. Implement a class `Codec` with two methods: - `encode(strs)` — takes a list (array) of strings and returns a single encoded string. - `decode(s)` — takes the encoded string and returns the original list (array) of strings. The machine handling `decode` does not know the original strings, so your encoding must be self-describing. Strings may contain **any** characters, including digits, spaces, and your delimiter, so a naive `join('/')` will not work. Your `decode(encode(strs))` must equal `strs` for every possible input.
Examples
["lint","code","love","you"]→["lint","code","love","you"]— encode then decode round-trips to the original list.["we","say",":","yes"]→["we","say",":","yes"]— Delimiter-like characters such as ':' inside a string must survive the round trip.["",""]→["",""]— Two empty strings differ from an empty list — length-prefixing preserves the count.
Constraints
- · 0 <= strs.length <= 200
- · 0 <= strs[i].length <= 200
- · strs[i] contains any possible characters out of 256 valid ASCII characters.
- · Your algorithm should be generalized enough to work on any possible set of characters.
- · Do NOT use class member/global variables to store state across encode/decode calls.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.