211.Design Add and Search Words Data Structure === ###### tags: `Medium`,`String`,`DFS`,`Trie` [211. Design Add and Search Words Data Structure](https://leetcode.com/problems/design-add-and-search-words-data-structure/) ### 題目描述 Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the `WordDictionary` class: * `WordDictionary()` Initializes the object. * `void addWord(word)` Adds `word` to the data structure, it can be matched later. * `bool search(word)` Returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `'.'` where dots can be matched with any letter. ### 範例 **Example 1:** ``` Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true] Explanation 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 ``` **Constraints**: * 1 <= `word.length` <= 25 * `word` in `addWord` consists of lowercase English letters. * `word` in `search` consist of `'.'` or lowercase English letters. * There will be at most 3 dots in `word` for `search` queries. * At most 10^4^ calls will be made to `addWord` and `search`. ### 解答 ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)