題目描述:設計將字串列表編碼為單一字串,以及將其解碼回原始列表的演算法(需處理任意字元,包括分隔符本身)。
解題思路:長度前綴法:將每個字串編碼為 <長度>#<字串>。例如 ["hello", "world"] 編碼為 "5#hello5#world"。解碼時,先讀到 #,取出長度 len,再讀取後面 len 個字元。這個方法不依賴特殊分隔符,對任意字元組合都有效。
時間複雜度:O(n) 編碼和解碼,n 為所有字串總字元數。
空間複雜度:O(n) — 編碼後字串大小與輸入成正比。
Encode: 1. For each string s: append len(s) + '#' + s Decode: 1. i = 0 2. While i < len(encoded): a. Find '#' at position j b. len = int(encoded[i:j]) c. Append encoded[j+1:j+1+len] to result d. i = j + 1 + len
計數作分隔符 O(n):用 len#string 格式編碼(如 4#testhi3#abc),解碼時讀取長度 — 標準且直觀。
使用特殊字符:將 # 視為轉義字符,編碼為 ##,複雜化處理。