208. Implement Trie (Prefix Tree)

 1class TrieNode:
 2    def __init__(self):
 3        self.children = {}
 4        self.is_end = False
 5
 6
 7class Trie:
 8
 9    def __init__(self):
10        self.root = TrieNode()
11
12    def insert(self, word: str) -> None:
13        node = self.root
14        for ch in word:
15            if ch not in node.children:
16                node.children[ch] = TrieNode()
17            node = node.children[ch]
18        node.is_end = True
19
20    def search(self, word: str) -> bool:
21        node = self.root
22        for ch in word:
23            if ch not in node.children:
24                return False
25            node = node.children[ch]
26        return node.is_end
27
28    def startsWith(self, prefix: str) -> bool:
29        node = self.root
30        for ch in prefix:
31            if ch not in node.children:
32                return False
33            node = node.children[ch]
34        return True
35
36
37# Your Trie object will be instantiated and called as such:
38# obj = Trie()
39# obj.insert(word)
40# param_2 = obj.search(word)
41# param_3 = obj.startsWith(prefix)

 1class Trie:
 2
 3    def __init__(self):
 4        self.root = {}
 5
 6    def insert(self, word: str) -> None:
 7        node = self.root
 8        for ch in word:
 9            if ch not in node:
10                node[ch] = {}
11            node = node[ch]
12        node["end"] = True
13
14    def search(self, word: str) -> bool:
15        node = self.root
16        for ch in word:
17            if ch not in node:
18                return False
19            node = node[ch]
20        return node.get("end", False)
21
22    def startsWith(self, prefix: str) -> bool:
23        node = self.root
24        for ch in prefix:
25            if ch not in node:
26                return False
27            node = node[ch]
28        return True
29
30
31# Your Trie object will be instantiated and called as such:
32# obj = Trie()
33# obj.insert(word)
34# param_2 = obj.search(word)
35# param_3 = obj.startsWith(prefix)