Tries
Tries store strings character by character, enabling O(L) operations on prefixes and words.
Lessons
1. Intro
Why tries matter
2. Trie Node Structure
Children for each character
3. Trie Insert Operation
Character by character
4. Trie Search Operation
Following the path
5. Prefix Search
The trie advantage
6. Problem - Implement Trie
The foundational trie problem
7. Trie Implementation
Complete solution
8. Implement Trie Solution
Build your trie
9. Counting Words with Prefix
Augmenting the trie
10. Trie Deletion
Removing words
11. Problem - Add and Search Word
Trie with wildcards
12. Wildcard Search Strategy
DFS for dot matching
13. Add and Search Solution
Implement your solution
14. Problem - Word Search II
Trie + backtracking
15. Word Search II: Trie Approach
Efficient multi-word search
16. Word Search II Optimizations
Pruning and cleanup
17. Word Search II Solution
Implement your solution
18. Problem - Longest Word in Dictionary
Trie with constraints
19. Longest Word Solution
BFS on valid paths
20. Compressed Tries (Radix Trees)
Space optimization
21. Suffix Tries and Suffix Trees
Pattern matching powerhouse
22. Problem - Maximum XOR of Two Numbers
Bitwise trie application
23. Bitwise Trie Concept
Numbers as bit strings
24. Maximum XOR Solution
Implement your solution
25. Problem - Search Autocomplete
Top-k suggestions
26. Autocomplete Design
Trie with rankings
27. Autocomplete Solution
Implement your solution
28. Problem - Replace Words
Trie for dictionary lookup
29. Replace Words Solution
Find shortest prefix match
30. Array vs Map Children
Implementation trade-offs
31. Trie Memory Optimization
Reducing space usage
32. Trie vs Hash Set
When to use which
33. Counting Distinct Substrings
Suffix trie application
34. Quiz: Tries
Test your understanding
35. Section Recap
What you learned
Practice Problems
Classic 01-trie for maximum XOR queries. Insert, delete, and find max XOR with given number.
Prefix XOR with binary trie. Maximize XOR of prefix and suffix using 01-trie queries.
01-trie with counting. Count elements where XOR with x is less than threshold.
Binary search with trie-like state tracking. Understand prefix properties in sequences.
String manipulation with prefix/suffix matching. Trie-like thinking for palindrome construction.
Monotonic stack with XOR. Combines stack technique with binary representation analysis.
XOR subsequence problem. Use prefix XOR with set to track achievable values.
Coordinate queries with trie-like structure for nearest neighbor in specific direction.
Minimize inversions after XOR. Binary trie to count inversions at each bit level.
Segment tree with merge properties. Trie-like divide for range maximum queries.
Count distinct substrings with constraints using trie. Classic string trie application.
Find string appearing as prefix, suffix, and middle. Z-function or trie approach.
Fundamental trie implementation. Insert, search, and startsWith operations.
Trie with wildcard search using DFS. Handle '.' matching any character.
Trie + DFS on grid. Find all words from dictionary in board. Prune with trie prefixes.
Binary trie for maximum XOR. Greedy bit-by-bit selection using trie traversal.
Replace words with shortest root in dictionary. Classic trie prefix matching.
Find longest word buildable character by character. Trie with valid word marking.
Autocomplete with trie. Return top 3 lexicographically smallest matches per prefix.
Trie storing sums at nodes. Sum values of all keys with given prefix.