Problem Statement
A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie()
Initializes the trie object.void insert(String word)
Inserts the stringword
into the trie.boolean search(String word)
Returnstrue
if the stringword
is in the trie (i.e., was inserted before), andfalse
otherwise.boolean startsWith(String prefix)
Returnstrue
if there is a previously inserted stringword
that has the prefixprefix
, andfalse
otherwise.
Example 1:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
Solution
The Trie below stores the following words:
- apple
- app
- any
- big
- bin
- bind
- catflowchart TD RT[root] N0[a] N1[p] N2[p*] N3[n] N4[y*] N5[b] N6[c] N7[l] N8[e*] N9[i] N10[g*] N11[a] N12[t*] N13[n*] N14[d*] RT-->N0 RT-->N5 RT-->N6 N0-->N1 N0-->N3 N3-->N4 N1-->N2 N2-->N7 N7-->N8 N5-->N9 N9-->N10 N6-->N11 N11-->N12 N9-->N13 N13-->N14A * indicates an end of word.
class Node:
def __init__(self, char=""):
self.char = char
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> Node:
"""
T: O(M) | M = word length; N = number of keys in Trie
S: O(M)
"""
node = self.root
# Traverse down the branch that spells out the word.
# Add nodes to extend the branch as necessary.
for char in word:
if char in node.children:
node = node.children[char]
else:
temp = Node(char)
node.children[char] = temp
node = temp
# Set the is_end flag to true to mark the end of the word
node.is_end = True
def search(self, word: str) -> bool:
"""
T: O(M)
S: O(1)
"""
node = self.root
# Traverse down the branch whose path is spelled out by
# the word. If a char is not a key in the children hash
# map, we know that the word doesn't exist in the Trie.
# If we get to the end of the branch and the is_end flag
# is False, we know that the word does not exist in the Trie.
for char in word:
if char in node.children:
node = node.children[char]
else:
return False
return node.is_end
def startsWith(self, prefix: str) -> bool:
"""
T: O(M)
S: O(1)
"""
node = self.root
# If a path can be spelled out by the chars in prefix,
# we have word that starts with prefix. If not, we don't.
for char in prefix:
if char in node.children:
node = node.children[char]
else:
return False
return True