MediumRating 1758
211. Design Add and Search Words Data Structure
stringdepth-first-searchdesigntrie
解題說明
Design Add and Search Words Data Structure
題目描述：設計資料結構，支援 addWord（新增單詞）和 search（搜尋單詞，. 可匹配任意單個字元）。
解題思路：以 Trie 為基礎。addWord 與普通 Trie 插入相同。search 需處理萬用字元 .：遇到普通字元正常走子節點；遇到 . 時，遞迴嘗試所有 26 個非空子節點。這個 DFS 回溯確保所有可能的匹配都被探索。
C++ 解法
複雜度分析
時間複雜度：addWord O(L)；search O(26^d × L/d) 最壞情況（d 為 '.' 數）。
空間複雜度：O(total characters × 26) — Trie 節點空間。
虛擬碼
search DFS(node, word, i): 1. If i == len(word): return node.isEnd 2. c = word[i] 3. If c != '.': check child c, recurse with i+1 4. If c == '.': try all 26 children recursively, return true if any match 5. Return false
其他解法
簡單雜湊表 O(n) 搜尋：存儲所有詞，搜尋時線性掃描並手動比對 — 時間複雜度更差。
正則表達式 O(n×|word|) 搜尋：編譯正則並匹配各詞 — 常數開銷大。
延伸思考
- 若要支持更複雜的模式（如
*任意子串）？ - 如何優化記憶體（壓縮 Trie）？
- 若詞表非常大，如何流式加載？