0211. 添加與搜索單詞 * 數據結構設計 · ttttt

# 0211. 添加與搜索單詞 \* 數據結構設計 ## 題目地址（211. 添加與搜索單詞 - 數據結構設計） <https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/> ## 題目描述 ``` <pre class="calibre18">``` 請你設計一個數據結構，支持添加新單詞和查找字符串是否與任何先前添加的字符串匹配。實現詞典類 WordDictionary ： WordDictionary() 初始化詞典對象 void addWord(word) 將 word 添加到數據結構中，之后可以對它進行匹配 bool search(word) 如果數據結構中存在字符串與 word 匹配，則返回 true ；否則，返回 false 。word 中可能包含一些 '.' ，每個 . 都可以表示任何一個字母。示例：輸入： ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] 輸出： [null,null,null,null,false,true,true,true] 解釋： WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True 提示： 1 <= word.length <= 500 addWord 中的 word 由小寫英文字母組成 search 中的 word 由 '.' 或小寫英文字母組成最調用多 50000 次 addWord 和 search ``` ``` ## 前置知識 - 前綴樹 ## 公司 - 阿里 - 騰訊 ## 思路我們首先不考慮字符"."的情況。這種情況比較簡單，我們 addWord 直接添加到數組尾部，search 則線性查找即可。接下來我們考慮特殊字符“.”，其實也不難，只不過 search 的時候，判斷如果是“.”, 我們認為匹配到了，繼續往后匹配即可。上面的代碼復雜度會比較高，我們考慮優化。如果你熟悉前綴樹的話，應該注意到這可以使用前綴樹來進行優化。前綴樹優化之后每次查找復雜度是O(h)O(h)O(h), 其中 h 是前綴樹深度，也就是最長的字符串長度。關于前綴樹，LeetCode 有很多題目。有的是直接考察，讓你實現一個前綴樹，有的是間接考察，比如本題。前綴樹代碼見下方，大家之后可以直接當成前綴樹的解題模板使用。 ![](https://img.kancloud.cn/34/0c/340c37fc6c68e2b73809d19d20a78a96_827x602.jpg) 由于我們這道題需要考慮特殊字符"."，因此我們需要對標準前綴樹做一點改造，insert 不做改變，我們只需要改變 search 即可，代碼(Python 3)： ``` <pre class="calibre18">``` def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curr = self.Trie for i, w in enumerate(word): if w == '.': wizards = [] for k in curr.keys(): if k == '#': continue wizards.append(self.search(word[:i] + k + word[i + 1:])) return any(wizards) if w not in curr: return False curr = curr[w] return "#" in curr ``` ``` 標準的前綴樹搜索我也貼一下代碼，大家可以對比一下： ``` <pre class="calibre18">``` def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curr = self.Trie for w in word: if w not in curr: return False curr = curr[w] return "#" in curr ``` ``` ## 關鍵點 - 前綴樹（也叫字典樹），英文名 Trie（讀作 tree 或者 try） ## 代碼 - 語言支持：Python3 Python3 Code：關于 Trie 的代碼: ``` <pre class="calibre18">``` class Trie: def __init__(self): """ Initialize your data structure here. """ self.Trie = {} def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ curr = self.Trie for w in word: if w not in curr: curr[w] = {} curr = curr[w] curr['#'] = 1 def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curr = self.Trie for i, w in enumerate(word): if w == '.': wizards = [] for k in curr.keys(): if k == '#': continue wizards.append(self.search(word[:i] + k + word[i + 1:])) return any(wizards) if w not in curr: return False curr = curr[w] return "#" in curr ``` ``` 主邏輯代碼： ``` <pre class="calibre18">``` class WordDictionary: def __init__(self): """ Initialize your data structure here. """ self.trie = Trie() def addWord(self, word: str) -> None: """ Adds a word into the data structure. """ self.trie.insert(word) def search(self, word: str) -> bool: """ Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. """ return self.trie.search(word) # Your WordDictionary object will be instantiated and called as such: # obj = WordDictionary() # obj.addWord(word) # param_2 = obj.search(word) ``` ``` ## 相關題目 - [0208.implement-trie-prefix-tree](208.implement-trie-prefix-tree.html) - [0212.word-search-ii](212.word-search-ii.html) - [0472.concatenated-words](problems/472.concatenated-words.md) - [0820.short-encoding-of-words](https://github.com/azl397985856/leetcode/blob/master/problems/820.short-encoding-of-words.md)