Encode and Decode Strings

String

20 min

Problem Statement

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

Example 1:

Input: ["lint","code","love","you"]

Encoded: "4#lint4#code4#love3#you"

Output: ["lint","code","love","you"]

Solution (Length-prefixed)

A robust way to encode a list of strings is to prefix each string with its length, followed by a delimiter. This allows us to know exactly how many characters to read for each string during decoding, even if the strings themselves contain the delimiter.

Algorithm Steps

Encode: For each string, prepend its length and a delimiter (e.g., '#'). Concatenate all these new strings together.
Decode: Iterate through the encoded string. At each step, find the delimiter to determine the length of the next string. Read that many characters to get the original string. Repeat until the end of the encoded string is reached.

Input (comma-separated):

Input: ["lint","code","love","you"]

Encoded:

Start encoding.

Encode and Decode Strings Solution


class Codec:
    def encode(self, strs: List[str]) -> str:
        res = ""
        for s in strs:
            res += str(len(s)) + "#" + s
        return res

    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])
            res.append(s[j+1 : j+1+length])
            i = j + 1 + length
            
        return res