Problem
Implement a Trie, also called a Prefix Tree, that supports the following operations:- insert(word) inserts a word into the Trie.
- search(word) returns
true if the complete word exists in the Trie.
- startsWith(prefix) returns
true if at least one word in the Trie starts with the given prefix.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
insert("apple")
search("apple")
search("app")
startsWith("app")
insert("app")
search("app")Output
true
false
true
true"apple" exists in the Trie, so search("apple") returns true.
The prefix
"app" exists, but it is not initially stored as a complete word, so search("app") returns false.
However,
startsWith("app") returns true because "apple" starts with "app".
After inserting
"app", it becomes a complete word, so search("app") returns true.
Solution
A Trie stores characters in a tree-like structure. Each node represents a character, and the path from the root to a node represents a prefix.Each node maintains references to its possible child characters and a boolean
isWord indicating whether a complete word ends at that node.
During insert, we traverse the Trie character by character. If a child for the current character does not exist, we create one. After processing the final character, we mark the node as the end of a word.
During search, we traverse the characters in the same way. The word exists only if we successfully reach its final character and that node is marked as
isWord.
For startsWith, we only need to successfully traverse the given prefix. It does not matter whether the final node represents a complete word.
class Trie {
private static class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isWord;
}
private final TrieNode root = new TrieNode();
public Trie() {
}
public void insert(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
// Mark the end of the complete word.
current.isWord = true;
}
public boolean search(String word) {
TrieNode node = findNode(word);
return node != null && node.isWord;
}
public boolean startsWith(String prefix) {
return findNode(prefix) != null;
}
private TrieNode findNode(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a';
if (current.children[index] == null) {
return null;
}
current = current.children[index];
}
return current;
}
}
Complexity
For a word or prefix of lengthL, each character is processed once, resulting in O(L) time complexity for insert, search, and startsWith.
Each Trie node stores a constant-size array of
26 children, so storing N total characters requires O(N) space.