A Trie is a structure based on a Tree structure that keeps trace of word as a Tree organization. Each word is represented as a sequence of nodes, each node being a letter of the word. Two words with their first letters in common have their first nodes in common.
class Trie:
def __init__(self):
self.trie = {} # A Trie is a Tree, represented as nested dictionnaries
def insert(self, word: str) -> None:
trie_tmp, word = self.trie, word + "#" # the # key represents the end of a word (pen# vs pencil)
for caracter in word:
if caracter not in trie_tmp:
trie_tmp[caracter] = {}
trie_tmp = trie_tmp[caracter]
def search(self, word: str) -> bool:
return(self.startsWith(word + "#"))
def startsWith(self, prefix: str) -> bool:
trie_tmp = self.trie
for caracter in prefix:
if caracter not in trie_tmp:
return(False)
trie_tmp = trie_tmp[caracter]
return(True)