LeetCode 271: Encode And Decode Strings — Step-by-Step Visual Trace

#leetcode #algorithms #python

Medium — String | Array | Design | Parsing

The Problem

Design an algorithm to encode a list of strings into a single string, then decode it back to the original list of strings. The encoded string should handle edge cases like empty strings and strings containing special characters.

Approach

The encoding uses a length-prefix format where each string is prefixed with its length followed by a delimiter '#'. During decoding, we parse the length, skip the delimiter, then extract exactly that many characters to reconstruct each original string.

Time: O(n) · Space: O(n)

Code

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

    def decode(self, s: str) -> List[str]:
        decoded = []
        i = 0
        while i < len(s):
            delimiter_pos = s.find("#", i)
            size = int(s[i:delimiter_pos])
            start_pos = delimiter_pos + 1
            end_pos = start_pos + size
            decoded.append(s[start_pos:end_pos])
            i = end_pos
        return decoded