Loading…
Loading…
Implement a trie (prefix tree): a tree that stores strings character by character, so that words sharing a prefix share the same path from the root.
Implement the Trie class:
Trie() initializes an empty trie.void insert(String word) adds word.boolean search(String word) returns true only if word was inserted as a complete word.boolean startsWith(String prefix) returns true if any inserted word begins with prefix.insert("apple")
search("apple") → true
search("app") → false ("app" is only a prefix so far)
startsWith("app") → true
insert("app")
search("app") → true
Example 1
Input: insert("apple"); search("apple") -> true; search("app") -> false; startsWith("app") -> true
Output: as shown
Explanation: "app" was never inserted as a complete word, so search returns false, but it IS a valid prefix of "apple", so startsWith returns true.
1 <= word/prefix length <= 2000Lowercase English letters onlyEach Trie node needs: a fixed-size array (or map) of child nodes, one per possible next character, and a boolean marking 'a complete word ends here.'
insert() walks the tree character by character, creating a new child node whenever the needed path doesn't exist yet.
search() and startsWith() share almost all their logic — the only difference is whether the final node needs isEndOfWord=true (search) or just needs to exist at all (startsWith).
class Trie {
private final TrieNode root = new TrieNode();
static class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord = false;
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) node.children[index] = new TrieNode();
node = node.children[index];
}
node.isEndOfWord = true; // mark the END of this specific word, not every node along the path
}
public boolean search(String word) {
TrieNode node = findNode(word);
return node != null && node.isEndOfWord; // must be a complete inserted word, not just any valid path
}
public boolean startsWith(String prefix) {
return findNode(prefix) != null; // just needs the path to exist — no isEndOfWord requirement
}
private TrieNode findNode(String s) {
TrieNode node = root;
for (char c : s.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) return null; // path doesn't exist
node = node.children[index];
}
return node;
}
}Time: O(L) per operation, L = word/prefix length · Space: O(N * L) total across all inserted words, N = word count