LC 271 - Encode and Decode Strings

Question

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.

Example 1:

Input: dummy_input = ["Hello","World"]
Output: ["Hello","World"]

Explanation:
Machine 1:
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 —msg—> Machine 2

Machine 2:
Codec decoder = new Codec();
String[] strs = decoder.decode(msg);

Example 2:

Input: dummy_input = [""]
Output: [""]

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?

Links

Question here and solution here

Solution

concept

The easy way to cheese the problem is to use a special token as delimiter (such as #$%) , but there is always a risk of the string itself contains the said delimiter.
A better way is to encode the length of the word + a delimiter. (dog -> 3#dog)
This way we can first get the length the word (i.e. read till #, in this case we get 3), then we select the next 3 char to get the word.
Even if the word contains # or some number it is ok since we will select the all 3 char after the first # due to how we encode (while we encode, we count the length of the word regardless it contains # or not.)

code

class Codec:
	"""
	uses special tokens
	"""
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string.
        """
        SEP = "#$%"
        return SEP.join(strs)

    def decode(self, s: str) -> List[str]:
        """Decodes a single string to a list of strings.
        """
        SEP = "#$%"
        return s.split(SEP)

class Codec:
	"""
	do not use special car
	"""
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string.
        """
        output = ""
        for s in strs:
            output += str(len(s)) + "#" + s
        return output

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

        while i < len(s):
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j])
            word = s[j + 1:j + 1 + length]
            output.append(word)
            i = j + 1 + length
        return output

Complexity

time: $O(n)$
space: $O(n)$