1 class Trie(object):
 2 
 3     def __init__(self):
 4         self.root = TrieNode()
 5 
 6     def insert(self, word):
 7         cur = self.root
 8         for i in word:
 9             cur = cur.children[i]
10         cur.is_word = True
11         
12 
13     def search(self, word):
14         cur = self.root
15         for i in word:
16             cur = cur.children.get(i)
17             if cur is None:
18                 return False
19         return cur.is_word
20 
21     def startsWith(self, prefix):
22         cur = self.root
23         for i in prefix:
24             cur = cur.children.get(i)
25             if cur is None:
26                 return False
27         return True
28         
29 class TrieNode(object):
30     def __init__(self):
31         self.children = collections.defaultdict(TrieNode)
32         self.is_word = False