Description
Implement lossless encode and decode for a list of strings, including empty strings and delimiter characters. Examples show decode(encode(input)).
Solution
def encode(strs):
return ''.join(str(len(s)) + '#' + s for s in strs)
def decode(s):
result = []
i = 0
while i < len(s):
separator = s.index('#',i)
size = int(s[i:separator])
i = separator+1
result.append(s[i:i+size])
i += size
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[["a#b","","12"]]- Output
["a#b","","12"]
Lengths distinguish delimiter text, an empty string, and digits.
Example 2
- Input
[[]]- Output
[]
An empty list encodes and decodes without entries.
Example 3
- Input
[[""]]- Output
[""]
One empty string must remain distinct from an empty list.
Approach
Prefix each string with its character count and a separator, then parse the length before reading that many characters.
Time & space
O(S) time and O(S) space, for total encoded size S. Each language's codec round-trips its own format.