解題說明
Encrypt and Decrypt Strings
題目描述： 設計一個加密解密系統。給定字母 keys 和對應的兩字元值 values。加密：將每個字母替換為對應的值。解密：給定一個加密字串，回傳有多少個 dictionary 中的字串加密後等於該字串。
解題思路： 加密是直接的映射。解密的關鍵觀察是：不要嘗試反向解密（因為 values 可能有重複，一個值可能對應多個字母），而是正向加密所有字典中的字串，統計每個加密結果的出現次數。
- 建立字母到值的映射（加密用）。
- 預處理：對 dictionary 中的每個字串做加密，用 hash map 統計每個加密結果出現的次數。
- encrypt(word)：逐字母查表替換。
- decrypt(word)：直接在 hash map 中查詢 word 出現的次數。
這是一個「逆向思維」的技巧：與其嘗試解密所有可能性（指數級），不如預計算所有合法字串的加密結果。
C++ 解法
複雜度分析
時間複雜度：建構子 O(D * L)（D 為字典大小，L 為平均字串長度），encrypt O(L)，decrypt O(L)（hash 查找）。
空間複雜度：O(D * L + K) — hash map 存所有加密結果，加密映射 O(K)。
虛擬碼
1. BUILD: Map each key to its value. Encrypt every dictionary word and count occurrences. 2. ENCRYPT(word): For each character, look up its mapped value. Concatenate all values. 3. DECRYPT(word): Return the count of dictionary words whose encryption equals word.
其他解法
-
Trie + 回溯解密：建立反向映射（每個兩字元值對應哪些字母）。對加密字串每兩個字元一組，嘗試所有可能的字母替換，在 Trie 中搜索。若找到字典中的字串則計數。最壞情況指數級，但 Trie 提供有效剪枝。
-
動態規劃解密：dp[i] 表示前 i 個字元的解密方式數。但仍需要檢查結果是否在字典中，不如預加密方法簡潔。
延伸思考
- 若 values 保證互不相同（即加密是一對一映射），解密是否可以直接反向映射？
- 若字典是動態的（可以加入或移除字串），如何高效維護 decCount？
- 若加密規則不是固定映射，而是根據字母位置變化的（如 Vigenère 密碼），如何修改系統？