Implement a Trie with insert(word), search(word) (exact match), and startsWith(prefix) (prefix match) operations.
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