LC 0208 [M] Implement Trie (Prefix Tree) - ALawliet/algorithms GitHub Wiki
class TrieNode:
def __init__(self):
self.word = False
self.children = {}
class Trie:
def __init__(self):
self.root = TrieNode()
# Inserts a word into the trie.
def insert(self, word):
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.word = True
# Returns if the word is in the trie.
def search(self, word):
cur = self.root
for c in word:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.word
# Returns if there is any word in the trie that starts with the given prefix.
def startsWith(self, prefix):
cur = self.root
for c in prefix:
if c not in cur.children:
return False
cur = cur.children[c]
return True
# Your Trie object will be instantiated and called as such:
# trie = Trie()
# trie.insert("somestring")
# trie.search("key")