Encode and Decode Strings

Medium Subject: Arrays & Hashing

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

Problem Statement

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and decoded back to the original list of strings.

Example 1:

Input: ["Hello","World"]
Output: ["Hello","World"]

Optimal Solution

Python

Approach: Length-Prefixed Encoding

We can encode each string by prefixing it with its length followed by a delimiter (like #), then the string itself. When decoding, we find the delimiter, parse the length before it, and extract the string.

class Solution:
    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