LeetCode 271 - Encode and Decode Strings

2026-04-07

medium　array

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.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
    // ... your code
    return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
    //... your code
    return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

And Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Example 1:

Input: dummy_input = ["Hello","World"]

Output: ["Hello","World"]

Explanation:
Machine 1:
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 ---msg---> Machine 2

Machine 2:
Codec decoder = new Codec();
String[] strs = decoder.decode(msg);

Example 2:

Input: dummy_input = [""]

Output: [""]

Constraints:

• 0 <= strs.length < 100
• 0 <= strs[i].length < 200
• strs[i] contains any possible characters out of 256 valid ASCII characters.

Solution 1:

class Solution:

    def encode(self, strs: List[str]) -> str:
        # Time Complexity: O(n), where n is the total number of characters across all strings.
        # Space Complexity: O(n), to store the newly created encoded string.

        # Explicitly handle the edge case of an empty list to distinguish [] from [""]
        if len(strs) == 0:
            return 'empty list'
        # Use a rare non-ASCII Unicode character (\u2556) as a delimiter.
        # This prevents the delimiter from conflicting with normal characters in the input strings.
        msg = '\u2556'.join(strs)
        return msg

    def decode(self, s: str) -> List[str]:
        # Time Complexity: O(n), where n is the length of the encoded string.
        # Space Complexity: O(n), to store the resulting list of strings.

        # Intercept the specific 'empty list' message and return an actual empty list
        if s == 'empty list':
            return []

        # Split the encoded string back into the original list using the same unique delimiter
        s_list = s.split('\u2556')
        return s_list

Solution 2:

class Solution:
    def encode(self, strs: List[str]) -> str:
        # Time Complexity: O(N), where N is the total number of characters across all strings.
        # Space Complexity: O(N), to store the encoded string components in the list.

        # Explicitly handle the edge case of an empty list to distinguish [] from [""]
        if len(strs) == 0:
            return 'empty list'

        msg = []
        for stri in strs:
            # Format: "length#string_content".
            # This ensures safe decoding regardless of what special characters the string contains.
            msg.append(f'{len(stri)}' + '#' + stri)

        # Using ''.join() is highly optimized in Python for string concatenation
        return ''.join(msg)

    def decode(self, s: str) -> List[str]:
        # Time Complexity: O(N), where N is the length of the encoded string.
        # Space Complexity: O(N), to store the decoded strings in the result list.

        # Intercept the specific 'empty list' message and return an actual empty list
        if s == 'empty list':
            return []

        msg = []
        i = 0  # Main pointer (i) tracks the start of the current string's length integer

        while i < len(s):
            j = i  # Explorer pointer (j) starts from i to find the delimiter '#'
            while s[j] != '#':
                j += 1

            # Extract the length of the string using the slice between i and j
            length = int(s[i: j])

            # Extract the actual string content precisely using the parsed length
            msg.append(s[j + 1: j + 1 + length])

            # Jump the main pointer directly to the start of the next encoded string
            i = j + 1 + length

        return msg

Takeaway

On the surface, this problem tests string manipulation. At its core, it is about serialization and protocol design in systems.

In real-world network communication, servers cannot transmit complex data structures like arrays directly — they must be serialized into a flat string.

The real challenge is designing an encoding scheme that is robust against edge cases such as empty strings or strings containing special characters. The length + delimiter + content format is a clean solution to this.

The two-pointer decode solution's principle of declaring the length before transmitting the payload directly mirrors how real network protocols like HTTP and TCP frame their packets.