271. Encode and Decode Strings

Problem Link

One of the most common pattern for encoding any data structure into stream of continuous data type is to use the size of data structure to denote the amount of data to read from stream for parsing single unit of data. But, since our data might also include numbers there would be no way to differentiate the size data from data structure value. To solve this, you can simply use a placeholder value between two of these values. This would lead us to create streams as follows -> <size><placeholder><data>...

Pseudocode

Encode: Since our data structure is simply list of strings, we can

• Calculate the size of each string
• Generate the encoded token for this string -> <size><placeholder><string>
• Join all the token strings to get encoded data.

Decode: You can use two pointers to indicate the start and current position in stream.

• We need to parse the stream until we reach end of it
• Start by parsing the size of next data token, by reading data until you encounter the placeholder value.
• Next decode the size into a number and read next size amount of data (skipping the placeholder).
• Update the start and current pointer to end of current token and continue.

Runtime Complexity

Time: \(O(n)\) <- encode, \(O(n)\) <- decode

Space: \(O(n)\) <- encode (from storing tokens/output), \(O(n)\) <- decode

PythonGo

class Solution:
    DELIMITER = "#"
    def encode(self, strs: List[str]) -> str:
        tokens = []
        for s in strs:
            token = f"{len(s)}{self.DELIMITER}{s}"
            tokens.append(token)

        return "".join(tokens)

    def decode(self, s: str) -> List[str]:
        start = curr = 0
        strs = []
        while curr < len(s):
            while s[curr] != self.DELIMITER:
                curr+=1

            size = int(s[start:curr])
            strs.append(s[curr+1: curr+size+1])
            start = curr+size+1
            curr = curr+size+1

        return strs

type Solution struct{}

func (s *Solution) Encode(strs []string) string {
    var tokens []string
    for _, str := range strs {
        tokens = append(tokens, fmt.Sprintf("%d#%s", len(str), str))
    }
    return strings.Join(tokens, "")
}

func (s *Solution) Decode(str string) []string {
    var strs []string
    var start, curr int
    for curr < utf8.RuneCountInString(str) {
        for str[curr] != '#' {
            curr++
        }
        size, _ := strconv.Atoi(str[start:curr])
        strs = append(strs, str[curr+1:curr+1+size])
        start = curr + 1 + size
        curr = start
    }
    return strs
}

---