A phone's autocomplete: after typing "ca", it only looks at words under the c-a branch.
Clues that point here
→ Prefix search, autocomplete
→ "Starts with"
→ Many words checked against a grid or a stream
→ Word dictionary with wildcards
Not this pattern when
✕ Only exact lookups (a HashSet is simpler)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Trie (Prefix Tree) · template
class Trie {
Trie[] next = new Trie[26];
boolean isWord;
void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.next[i] == null) node.next[i] = new Trie();
node = node.next[i];
}
node.isWord = true;
}
}