类似208，Trie树操作，注意本题存在通配符'.'，所以search操作需要DFS实现
1 #211
2 #Runtime: 10694 ms (Beats 62.94%)
3 #Memory: 119.7 MB (Beats 22.35%)
4
5 class TrieNode:
6 def __init__(self):
7 self.sons = {}
8 self.eow = False
9
10
11 class WordDictionary(object):
12
13 def __init__(self):
14 self.root = TrieNode()
15
16 def addWord(self, word):
17 """
18 :type word: str
19 :rtype: None
20 """
21 r = self.root
22 for ch in word:
23 if ch not in r.sons:
24 r.sons[ch] = TrieNode()
25 r = r.sons[ch]
26 r.eow = True
27
28
29 def search(self, word):
30 """
31 :type word: str
32 :rtype: bool
33 """
34 def DFS(r, depth):
35 if depth == len(word):
36 return r.eow
37 if word[depth] == '.':
38 for ch in r.sons:
39 if DFS(r.sons[ch], depth + 1):
40 return True
41 if word[depth] in r.sons:
42 return DFS(r.sons[word[depth]], depth + 1)
43 return False
44 return DFS(self.root, 0)
45
46
47
48 # Your WordDictionary object will be instantiated and called as such:
49 # obj = WordDictionary()
50 # obj.addWord(word)
51 # param_2 = obj.search(word)