Tries
Start typing a word and your phone narrows the guesses with every letter. After two letters you are already on the right page for every word that starts that way. A trie stores words the same way, sharing each prefix once so a lookup only walks the letters you type.
2 · Watch
No sound? Captions are on by default.
3 · Now you drive
Keys:←→ stepSpace playR reset
Implement Trie (Prefix Tree)
or try
Up to 4 words of 1–6 letters (a–z), then | and a word to look up.Start with an empty root.Step 1 of 16. Empty trie, just a root node. 2 words to insert, then look up “app”.
Step 1 of 16
solution.ts▶ marks the line running now
class TrieNode {
children = new Map<string, TrieNode>();
isWord = false;
}
function insert(root: TrieNode, word: string) {
let node = root;
for (const ch of word) {
if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
node = node.children.get(ch)!;
}
node.isWord = true;
}
function search(root: TrieNode, word: string, prefix = false) {
let node = root;
for (const ch of word) {
const next = node.children.get(ch);
if (!next) return false;
node = next;
}
return prefix || node.isWord;
}
4 · Your turn
0 of 3 problems solved
- Medium01
Implement Trie (Prefix Tree)
The one you just watched. Write it from memory.
- Medium02
Design Add and Search Words Data Structure
Trie search where “.” matches any letter at that spot.
- Hard03
Word Search II
Walk the board and the trie together, pruning dead letters.