Encode and Decode Strings

Problem Source: Leetcode

Problem Description

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement encode and decode methods.

You are not allowed to solve the problem using any serialize methods (such as eval).

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] contains any possible characters out of 256 valid ASCII characters.

Follow up: Could you write a generalized algorithm to work on any possible set of characters?

tests

def test(fn):
    codec = fn()
    
    expected = ["Hello","World"]
    expected_str = '5#Hello5#World'
    actual_str = codec.encode(expected)
    assert actual_str == expected_str
    actual = codec.decode(actual_str)
    assert actual == expected

    expected = [""]
    expected_str = '0#'
    actual_str = codec.encode(expected)
    assert actual_str == expected_str
    actual = codec.decode(actual_str)
    assert actual == expected

Solution

• Time Complexity: O(n)
• Space Complexity: O(1)

from typing import List
class Codec:
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string.
        """
        encoded_str = ''
        for s in strs:
            encoded_str += str(len(s)) + '#' + s
        return encoded_str

    def decode(self, s: str) -> List[str]:
        """Decodes a single string to a list of strings.
        """
        i,l = 0,0

        out = []
        while i < len(s):
            if s[i] != '#':
                l = l * 10 + int(s[i])
                i += 1
            else:
                out.append(s[i+1:i+1+l])
                i = i + 1 + l
                l = 0
        return out
test(Codec)