Encode and Decode Strings

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

• 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 encode(str[] strs) -> str, and machine 2 has the function decode(str s) -> str[]

Solution

• My initial solution was to split the strings by a specific delimiter, but that fails whenever the strings that you are trying to encode include the specific delimiter character.
• Instead, we can encode the length of the strings, along with a delimiter. For instance, given ["hello", "world"], it’ll encode as "5:hello5:world".
  • To decode this, we can search the string for the delimiter occurrences, and keep track of the index. Then, we get the left part which will be the length.
  • Once we get the length, we simply get the start and end of the string via the position of the : character, (+ 1 for the start, and + length for the end)
  • Then, we append the string from start to end to the response array and set the new start to be end, so we continue onto the next chunk.

class Solution:
    def encode(self, strs: List[str]) -> str:
        return "".join(f"{len(s)}:{s}" for s in strs)
 
    def decode(self, s: str) -> List[str]:
        res = []
        i = 0
 
        while i < len(s):
            j = i
 
            while s[j] != ":":
                j += 1
 
            length = int(s[i:j])
            start = j + 1
            end = start + length
 
            res.append(s[start:end])
            i = end
 
        return res
 

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───