Templates
Template: 15. TRIE
Mark when done:
15. TRIE
# =============================================================================
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None
def _find(self, word):
node = self.root
for ch in word:
if ch not in node.children:
return None
node = node.children[ch]
return node
# =============================================================================