題目網址：https://leetcode.cn/problems/encode-and-decode-strings/

題意：給一 string list strs, 請設計一演算法, 讓 encode 後的 string 可以透過網路高效傳輸, 並透過 decode 還原回原本的 string list。

注意：

  • string 可能會包含所有的 ASCII char, 所以你設計的演算法要能處理任何可能出現的 char
  • 請勿使用 class member、global variable、static variable 來儲存額外的狀態

Solution：

想法：不能只在兩個 string 間只用一個分隔符 (delimiter) 隔開, 因為也有可能 input 中恰好有該分隔符組成的 string

e.g. delimiter = '#', strs = ['1', '2#3']

這樣會得到錯誤的答案 ['1', '2', '3'], 而非 ['1', '2#3']

因此, 要額外紀錄每個 string 的長度：

  • Encode 時, 在每個 string s 前面加上長度 s.size() 和分割符 #
  • Decode 時, 首先找出 idx i 往後的第一個 #, 假設其 idx 為 j, 則 s[i, j) 轉成 int 後即為 s 的長度。從 j + 1 往後(含)取 s[i, j) 個 char 即可得到當前的 s
class Codec {
public:

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        stringstream ss;
        for (const auto& s : strs) {
            ss << s.size() << '#' << s;
        }
        return ss.str();
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        if (s.empty()) {
            return {};
        }

        int i = 0, n = s.size();
        vector<string> res;

        while (i < n) {
            int j = i;
            while (s[j] != '#') {
                ++j;
            }
            const int len = stoi(s.substr(i, j - i));
            res.emplace_back(s.substr(j + 1, len)); // push 當前的 string
            i = j + 1 + len; // 更新下一次開始的位置
        }
        return res;
    }
};
  • time：
    • encode：$O(n)$ ➔ n 為 strs 中所有 string 的總長度
    • decode：$O(n)$ ➔ n 為 s 的長度
  • space：$O(n)$ ➔ 皆需要 $O(n)$ 來儲存原先所有的 string