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().