TrieNode with children map and isEnd flag.
class TrieNode: def init(self): self.children = {} self.isEnd = False
class Trie: def init(self): self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.isEnd = True
def search(self, word):
node = self._traverse(word)
return node is not None and node.isEnd
def startsWith(self, prefix):
return self._traverse(prefix) is not None
def _traverse(self, s):
node = self.root
for char in s:
if char not in node.children:
return None
node = node.children[char]
return node
per operation.