Lesson 19.3 · Trie
Trie + DFS: Wildcards and Word Grids
When a query branches (a wildcard character, or a path through a grid), explore the trie with DFS and prune as soon as no child matches.
12 min
Think of it like this
Solving a crossword with a dictionary sorted by prefix: the moment the letters you have don't start any word, you stop trying that direction.
1.Two kinds of branching
Wildcards: in a search like b.d, a . can be any letter, so at that position you try every non-null child. Fixed letters still follow one child.
Word grids (Word Search II): instead of searching the grid once per word, put all the words in a trie and start a DFS from every cell, walking the trie in step with the grid. If the trie has no child for the next letter, that whole branch is pruned, for every word at once.
Store the full word at its end node; when the DFS reaches it, record the word and clear it so it's reported once.
Quick check
Why is one trie better than running single-word search for each of 1000 words?
Remember
- Wildcard: try every child.
- Grid: walk grid and trie together; prune on a missing child.
- Mark found words so each is reported once.
Common mistakes
- Forgetting to restore the grid cell after backtracking.