實現(xiàn)Trie樹的三種操作：插入、查找是否包含某個單詞，以及是否包含某個前綴
1 #208
2 #Runtime: 184 ms (Beats 54.16%)
3 #Memory: 40.8 MB (Beats 42.22%)
4
5 class Node:
6 def __init__(self):
7 self.sons = {}
8 self.eow = False
9
10
11 class Trie(object):
12
13 def __init__(self):
14 self.root = Node()
15
16
17 def insert(self, word):
18 """
19 :type word: str
20 :rtype: None
21 """
22 r = self.root
23 for ch in word:
24 if ch not in r.sons:
25 r.sons[ch] = Node()
26 r = r.sons[ch]
27 r.eow = True
28
29
30 def search(self, word):
31 """
32 :type word: str
33 :rtype: bool
34 """
35 r = self.root
36 for ch in word:
37 if ch not in r.sons:
38 return False
39 r = r.sons[ch]
40 return r.eow
41
42
43 def startsWith(self, prefix):
44 """
45 :type prefix: str
46 :rtype: bool
47 """
48 r = self.root
49 for ch in prefix:
50 if ch not in r.sons:
51 return False
52 r = r.sons[ch]
53 return True
54
55
56
57 # Your Trie object will be instantiated and called as such:
58 # obj = Trie()
59 # obj.insert(word)
60 # param_2 = obj.search(word)
61 # param_3 = obj.startsWith(prefix)