Encode and Decode Strings

Problem

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

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

Implement the encode and decode methods:

• encode(strs) encodes a list of strings to a single string.

• decode(s) decodes a single string to a list of strings.

The strings may contain any possible characters out of 256 valid ASCII characters, so no character can be reserved as a delimiter.

Example 1:

Input: strs = ["hello","world"]
Output: ["hello","world"]
Explanation: The encoded string is sent over the network and decoded
back to the original list.

Example 2:

Input: strs = [""]
Output: [""]

Constraints:

• 0 <= strs.length <= 200

• 0 <= strs[i].length <= 200

• strs[i] contains any possible characters out of 256 valid ASCII characters.

Follow up: Could you write a generalized algorithm to work on any possible set of characters?

Pattern

Array, String, Design

Approaches

Length Prefix

Code

class Codec:
    """An algorithm that encodes and decodes a list of strings as a string."""

    def encode(self, strs: list[str]) -> str:
        """Encode ``strs`` into a single string using length prefixes."""
        if strs == []:
            return ""

        s = ""
        for t in strs:
            s += str(len(t)) + "#" + t
        return s

    def decode(self, s: str) -> list[str]:
        """Decode ``s`` back into the original list of strings."""
        if s == "":
            return []

        strs = []
        i = 0
        while i < len(s):
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j])
            i = j + 1
            strs.append(s[i : i + length])
            i = i + length

        return strs

Test

>>> from encode_and_decode_strings__length_prefix import Codec
>>> c = Codec()
>>> c.decode(c.encode(["hello", "world"]))
['hello', 'world']
>>> c.decode(c.encode([""]))
['']
>>> c.decode(c.encode([]))
[]

class encode_and_decode_strings__length_prefix.Codec

Bases: object

An algorithm that encodes and decodes a list of strings as a string.

decode(s: str) → list[str]

Decode s back into the original list of strings.

encode(strs: list[str]) → str

Encode strs into a single string using length prefixes.