0271. Encode and Decode Strings

Problem Category:: Array Neetcode Category:: Arrays and Hashing

https://leetcode.com/problems/encode-and-decode-strings/

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

Method 1

Chunked transfer encoding

Data stream is divided into chunks. Each chunk is preceded by its size in bytes.

TBC

Method 2

Delimiters with length encoding

Although a normal delimiter between each string by itself works okay, it will fail in the case where any string contains the delimiter too

• By encoding the length of each string prior to the delimiter, we avoid this
• Time complexity : $O(N)$ where $N$ is a number of strings in the input array.

Python implementation

class Codec:
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string.
        """
        res = []
        for word in strs:
            res.extend([str(len(word)), "#", word])
        print(''.join(res))
        return ''.join(res)
        
 
    def decode(self, s: str) -> List[str]:
        """Decodes a single string to a list of strings.
        """
        res = []
        i = 0
        while i < len(s):
            #alt: s.find("#", start = i)
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j]) #len encoded before "#""
            res.append(s[(j+1):(j+1+length)]) # word starts after "#"
            i = j + 1 + length
        return res
            
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))