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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment