Tries problems, grouped by pattern
A trie stores words character by character so prefix queries cost the length of the prefix, not the size of the dictionary. Build one by hand before reaching for it in word search and autocomplete problems.
When to reach for it
- Many prefix lookups on a word list
- Autocomplete or starts-with queries
- Counting words that share a prefix
Mistakes to watch for
- Confusing "prefix exists" with "word exists"
- Not decrementing counts on erase
- Fixed 26-child arrays with non-lowercase input
The 2 problems
1Basics
- Implement Trie (Prefix Tree) Animated Medium
- Implement Trie ll Animated Medium