Trie
A tree of character edges. Each path from the root spells a prefix and terminal flags mark whole words.
TriesO(L) per operationNew11 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
prefix search
autocomplete
word dictionary with wildcards
word search II
The template
Get this into muscle memory, then adapt the condition per problem.
class Node { children = new Map<string, Node>(); end = false; }
let cur = root;
for (const ch of word) {
if (!cur.children.has(ch)) cur.children.set(ch, new Node());
cur = cur.children.get(ch)!;
}
cur.end = true; Watch Trie (Prefix Tree)If you are stuck
The generic hint ladder for this pattern, in order.
- 1Repeated prefix lookups across a dictionary suggest sharing prefixes.
- 2Each node holds edges for the next character.
- 3Pair the trie with DFS on a board to prune impossible branches early.
Drill it
Every problem in the bank that uses this pattern.
0 / 11 solved