Encode and Decode Strings 解題教學:3 種解法完整比較|LeetCode 271 Best Practice

Encode and Decode Strings 解題教學示意圖|LeetCode 271

本文完整拆解 LeetCode 271 Encode and Decode Strings 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Encode and Decode Strings 一次弄懂。

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

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.

You are not allowed to solve the problem using any serialize methods (such as eval).

 

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:

  • 1 <= 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?

				
					# time complexity: O(n)
# space complexity: O(n)
from typing import List


class Codec:
    def __init__(self) -> None:
        self.stringIndex = []
        pass

    def encode(self, strs: List[str]) -> str:
        encodeString = ""
        for string in strs:
            currentIndex = len(string)
            self.stringIndex.append(currentIndex)
            encodeString += string
        print(self.stringIndex)
        return encodeString

    def decode(self, s: str) -> List[str]:
        decodeList = []
        for i, item in enumerate(self.stringIndex):
            decodeList.append(s[:item])
            s = s[item:]
        return decodeList


# Your Codec object will be instantiated and called as such:
codec = Codec()

dummy_input = ["Hello", "World"]
print(codec.encode(dummy_input))
print(codec.decode("HelloWorld"))
				
			

Encode and Decode Strings 解題思路

這題的陷阱是「分隔符可能出現在字串內容裡」,所以不能單純用逗號或 # 串接。正確做法是長度前綴編碼:每個字串前面先寫它的長度,再寫一個固定分隔符,最後接內容。解碼時先讀長度,就能精準切出內容,完全不受內容字元影響。

Encode and Decode Strings 演算法步驟

  1. 編碼:對每個字串 s,輸出 s.length + “#” + s,全部串接起來。
  2. 解碼:用指標 i 從 0 開始掃描。
  3. 從 i 往後找到第一個 “#”,中間的數字就是長度 len。
  4. 從 “#” 後面取 len 個字元當作一個字串,把 i 跳到該字串之後,重複直到結尾。

Encode and Decode Strings 複雜度分析

項目複雜度
時間複雜度O(n)
空間複雜度O(n)

n 是所有字串的總長度。編碼與解碼都只線性走訪一次,時間為 O(n)。輸出字串長度與原資料同級,空間為 O(n)。

Encode and Decode Strings 的邊界情況與常見錯誤

  • 空字串要能正確編碼成 “0#”,解碼後仍是空字串。
  • 內容裡含有 “#” 或數字完全不影響,這正是長度前綴的優點。
  • 長度可能是多位數,解碼時要讀到第一個 “#” 為止而非只讀一個字元。
  • 空陣列編碼後是空字串,解碼要回傳空陣列。

Encode and Decode Strings 其他解法比較

解法時間空間說明
用罕見字元當分隔符O(n)O(n)內容一旦出現該字元就壞掉
用跳脫字元轉義分隔符O(n)O(n)可行但編解碼邏輯變複雜
長度前綴編碼O(n)O(n)本文採用,最穩健