211. Design Add and Search Words Data Structure
設計一個系統可以支援加新字(addWord)以及搜尋(search)字是否在系統的功能
具體來說就是要實作一個WordDictionary的類別，並有以下幾個函數
1. WordDictionary: 初始化WordDictionary物件
2. void addWord(word): 加word到設計的系統中，以便做後續查找的功能
3. bool search(word): 從系統中找是否有符合word的字被加入，特別需要注意word中可
能會有'.'字元，代表的意思是可以是任何字母，也就是如果word是"w.a"則"waa" ~ "wza
"都是符合的答案
例子:
輸入
["WordDictionary","addWord","addWord","addWord","search","search","search","se
arch"]
[[],["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: 每個字的長度，大於等於1，小於等於25
2, 3: word在addWord或是search的函數中只會有小寫字母
4: 最多只會有三個'.'在search函數的參數word中
5: 最多只會呼叫addWord和search各10^4次
解題想法:
看到字串查找，我第一個想法就是Trie，那至於如何去支援search就得依靠dfs的思維去
遞迴查找答案
以這樣的做法底下，時間複雜度addWord最多就是25 * 10^4,而search就會是25*25*25*10
^4，這複雜度其實是會TLE，不知道有沒有更快的做法，反正我是想不到orz
C++ code