Encode and Decode Strings
Problem Statement
Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.
Please implement encode
and decode
Example 1:
Input: ["python","code","love","you"]Output:["python","code","love","you"]
Example 2:
Input: ["we","say",":","yes"]Output: ["we","say",":","yes"]
Constraints:
0 <= strs.length < 100
0 <= strs[i].length < 200
strs[i]
contains only UTF-8 characters.
You should aim for a solution with O(m)
time and O(1)
space for each encode()
and decode()
call, where m
is the sum of lengths of all the strings.
Recommended Time and Space Complexity
You should aim for a solution with O(m)
time and O(1)
space for each encode()
and decode()
call, where m
is the sum of lengths of all the strings.
Hint 1
A naive solution would be to use a non-ascii character as a delimiter. Can you think of a better way?
Hint 2
Try to encode and decode the strings using a smart approach based on the lengths of each string. How can you differentiate between the lengths and any numbers that might be present in the strings?
Hint 3
We can use an encoding approach where we start with a number representing the length of the string, followed by a separator character (let’s use #
for simplicity), and then the string itself. To decode, we read the number until we reach a #
, then use that number to read the specified number of characters as the string.
Solution
Encoding & Decoding
def encode(strs: list[str]) -> str: if not strs: return "" sizes = [str(len(s)) for s in strs] res = ",".join(sizes) + ",#" + "".join(strs) return res
def decode(s: str) -> list[str]: if not s: return [] i = 0 sizes = [] while s[i] != '#': cur = "" while s[i] != ',': cur += s[i] i += 1 sizes.append(int(cur)) i += 1 i += 1 res = [] for sz in sizes: res.append(s[i:i + sz]) i += sz return res
Time complexity: O(m)
for encode()
and decode()
. Space complexity: O(n)
for encode()
and decode()
.
Encoding & Decoding (Optimal)
def encode(strs: list[str]) -> str: res = "" for s in strs: res += str(len(s)) + "#" + s return res
def decode(s: str) -> list[str]: res = [] i = 0
while i < len(s): j = i while s[j] != '#': j += 1 length = int(s[i:j]) i = j + 1 j = i + length res.append(s[i:j]) i = j
return res
Time complexity: O(m)
for encode()
and decode()
. Space complexity: O(1)
for encode()
and decode()
.