#208
Implement Trie (Prefix Tree)
Medium Trie basics
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Build a trie with insert(word), search(word) (exact word) and startsWith(prefix).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: build insert, search and startsWith.
Why this works: walk one node per letter; search also needs the end flag, startsWith doesn't.
Example: insert "apple"
search "app" → path exists, but no end flag → falsestartsWith "app" → true
✦Hints open one at a time
Each node has up to 26 children and a flag saying "a word ends here".
search and startsWith walk the same way; they differ only in whether the end flag is required.
↗Approach
Node with TrieNode[26] children and boolean end. insert creates missing children along the path and sets end. A shared walk(s) helper returns the node reached, or null.
</>Solution (Java)
class Trie {
private static class Node {
Node[] next = new Node[26];
boolean end;
}
private final Node root = new Node();
public void insert(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (cur.next[i] == null) cur.next[i] = new Node();
cur = cur.next[i];
}
cur.end = true; // a whole word ends here
}
public boolean search(String word) {
Node n = walk(word);
return n != null && n.end;
}
public boolean startsWith(String prefix) {
return walk(prefix) != null;
}
private Node walk(String s) {
Node cur = root;
for (char c : s.toCharArray()) {
cur = cur.next[c - 'a'];
if (cur == null) return null;
}
return cur;
}
}!Common mistake
Returning true from search when the word is only a prefix of an inserted word — check the end flag.
Complexity
- Time: O(L) per operation.
- Space: O(total characters inserted).
Topic: Trie
🎬 Episode 97: video coming soon