Medium
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 string word
into the trie.boolean search(String word)
Returns true
if the string word
is in the trie (i.e., was inserted before), and false
otherwise.boolean startsWith(String prefix)
Returns true
if there is a previously inserted string word
that has the prefix prefix
, and false
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
Constraints:
1 <= word.length, prefix.length <= 2000
word
and prefix
consist only of lowercase English letters.3 * 104
calls in total will be made to insert
, search
, and startsWith
.To solve the task, here are the steps for implementing the Trie (Prefix Tree) problem:
TrieNode
to represent each node in the trie.__init__
method for the Trie class to initialize an empty trie with a root node.insert
method to insert a word into the trie.search
method to check if a word exists in the trie.startsWith
method to check if there is any word in the trie that starts with a given prefix.Here’s a Python implementation:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# Example Usage
trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # Output: True
print(trie.search("app")) # Output: False
print(trie.startsWith("app")) # Output: True
trie.insert("app")
print(trie.search("app")) # Output: True
This solution efficiently implements the Trie data structure and satisfies the requirements of the problem.