This is the implementation of trie in python3, you can get the question from implement-trie-prefix-tree.
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
self.end_of_word = '#'
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end_of_word] = self.end_of_word
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.end_of_word in node
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
We use dict to store the value.
self.root = {}
When we insert a word, we will find every char in the word from node which is initiated to root.
node = self.root
Then we use setdefault to get the value by the char as key. If char is not in the node, node[char] will be {}.
For example, after inserted test, the root will be as blow:
{'t': {'e': {'s': {'t': {'#': '#'}}}}}
As the implementation of the insert function, when we search a word, we will find each char in the word from the node
which is initiated to root. If the char does not exit in node, return False, otherwise, continue to search the next char.
After all chars have been found, we should check if end_of_word is included in node, for we may just found the prefix,
not the word.
The last function is startsWith, it is almost the same as search. But it does not care about if end_of_word is in node.