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 < 1000 <= strs[i].length < 200strs[i] contains any possible characters out of 256 valid ASCII characters.

• 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

結語：

這道題表面上考驗字串操作，核心其實是系統設計中的***「序列化 (Serialization)」與「通訊協定設計」***。

在真實的網路傳輸中，伺服器間無法直接傳遞陣列等複雜結構，必須將資料轉換成連續的字串。

這題真正考驗的是我們能否設計出具備高度防禦力的編碼規則（例如採用 長度 + 分隔符號 + 內容），來完美避開空字串或資料內含特殊符號等極端邊界測資（Edge Cases）。

這套利用雙指針精準切割的解法，其***「先宣告長度、再傳送主體」***的思維，更直接呼應了 HTTP 與 TCP 封包等真實網路底層的傳輸標準。