‣
from collections import defaultdict
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
# self.isWord = False
self.children = defaultdict(Trie)
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
node = self
for l in word:
node = node.children[l]
# node.isWord = True
node.children["-"] # optimize for memory
def search(self, word, node=None):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self
for l in word:
if l in node.children:
node = node.children[l]
else:
return False
return "-" in node.children
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that
starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self
for l in prefix:
if l in node.children:
node = node.children[l]
else:
return False
return True