解題說明
Replace Words
題目描述：給定一個字典 dictionary（包含許多「字根」root）以及一個句子 sentence。句子由空格分隔的單詞組成。對句子中的每個單詞，若字典中存在某個字根是該單詞的前綴，則將該單詞替換為最短的符合條件的字根；若有多個字根都是其前綴，取最短的那個。最後回傳替換後的句子字串。
解題思路：最直觀的方法是對每個單詞逐一與字典比對，但字典可能很大，效率不佳。更好的做法是先將所有字根插入 Trie（前綴樹），再對句子中的每個單詞在 Trie 中搜尋：從根節點開始，逐字元往下走；若走到某個節點是某字根的結尾（is_end = true），立即回傳該字根作為替換結果；若走到底都沒找到完整字根，則保留原單詞不變。這樣每個單詞的查詢時間為 O(L)（L 為單詞長度），遠優於暴力比對。整體流程：建 Trie → 分詞 → 對每個詞查詢最短字根前綴 → 拼接結果。
C++ 解法
複雜度分析
時間複雜度：O(D + S)，其中 D 為所有字根的字元總數（建 Trie），S 為句子的字元總數（查詢每個單詞）。每個字元最多被處理一次，整體線性。
空間複雜度：O(D × 26)——Trie 儲存所有字根，每個節點有 26 個子指標；O(D) 若使用 unordered_map 替代固定陣列。輸出字串額外使用 O(S) 空間。
虛擬碼
1. Build a Trie by inserting every root from the dictionary. - Mark the last node of each root with is_end = true. 2. Split sentence into individual words (by spaces). 3. For each word: a. Traverse the Trie character by character. b. If at any node is_end == true, replace word with the prefix seen so far. c. If traversal ends without finding a root, keep the original word. 4. Join all (possibly replaced) words with spaces and return.
其他解法
方法一：暴力字典查詢 對每個單詞，遍歷字典中所有字根，找出所有是該單詞前綴的字根，取最短者。時間複雜度 O(S × D_count × L)，當字典很大時效率差，但程式碼簡單、適合小輸入。
方法二：HashSet 前綴查詢
將字典中所有字根存入 unordered_set，對每個單詞從長度 1 開始逐漸截取前綴並在 HashSet 中查找，找到第一個命中者即回傳。時間複雜度 O(S × L)（L 為單詞最長長度），空間 O(D)，比 Trie 簡潔但常數較大，且無法享受 Trie 共享前綴節省空間的優勢。
方法三：排序後 lower_bound 將字典排序，對每個單詞用二分查找找到最接近的字根，再驗證是否為前綴。時間複雜度 O(D log D + S × log D × L)，適合字典不可修改且需節省空間的場景。
延伸思考
- 若句子中同一個單詞出現多次，如何加入快取（memoization）避免重複查詢 Trie，進一步加速？
- 若字典允許動態新增或刪除字根，Trie 相較於 HashSet 有何優勢？刪除節點時需要注意什麼？
- 將本題延伸：若要找的不是「最短前綴字根」而是「最長前綴字根」，Trie 的查詢邏輯需要如何修改？