Tries
A trie that steers another search
The payoff. You solved the grid search one unit ago; the trie is what makes it work for many words at once.
The problem, and the obvious approach
You have a grid of letters and a list of words, and you must report which words can be traced through adjacent cells without reusing a cell.
You solved the single-word version in Unit 10. The obvious extension is to run that search once per word, which is correct and costs the full grid search multiplied by the number of words. With a large dictionary that is far too slow.
Why it works
Walk the grid once, carrying the trie
Turn it around. Instead of asking for each word whether the grid contains it, walk the grid once and ask at every step which words are still possible.
A trie answers that. Carry a trie node alongside the grid position. Stepping to a neighboring cell is only worth doing if that cell's letter is a child of the current trie node. If it is not, no word in the entire dictionary continues this way, and the branch dies immediately.
That is the pruning, and it is doing an enormous amount of work: one failed lookup rules out every word sharing that dead prefix.
The search is Unit 10's grid backtracking with one extra parameter and one extra guard. The guard is worth seeing on its own, because it is where all the saving comes from.
Below, no search runs at all. Every cell of a small board is simply asked whether any word in the dictionary could begin there.
Tip
What that lookup is really worth
zzz costs almost nothing here: no cell holds a z, so it dies at the first lookup from every start. With a real dictionary most words die that cheaply, and none of them cost a separate grid search.
That is the whole argument for carrying the trie rather than looping over words. A failed lookup does not rule out one word, it rules out every word sharing that dead prefix, and the deeper the failure the more words it takes with it.
Tip
Store the word, not just a flag
Keeping the whole word on its end node means that when the search arrives there, the answer is available with no need to have tracked the path.
That removes a whole piece of bookkeeping. The alternative is to build the string as you descend and read it at the end, which works and requires one more thing to keep correct through the undo.
Why it works
Clearing the word prevents duplicates
The same word can be reachable by several paths, and it should be reported once. Setting the stored word to None after recording it is the simplest deduplication and costs nothing.
It also means the search never stops early at a found word, which matters: a found word may be a prefix of a longer one still to be found, so the exploration must continue past it.
Tip
Paths bend, and one path can spell two words
On the board above, oa and oat occupy the same path, and the longer one is only reachable by continuing past the point where the shorter one completed. A search that stopped at a found word would miss it.
ate runs through the same four cells in a different direction, starting at the a and turning a corner. Paths bend, so when you sketch a case by hand do not test only straight lines; a solution that walks in one direction per start passes an alarming number of small examples.
Cost
What this actually buys
The naive approach is the grid search once per word. The trie version is a single grid search whose branching is bounded by the trie, so the dictionary size stops multiplying the cost and only affects how much of the trie exists.
There is a further optimization worth naming: pruning trie nodes that have no remaining words beneath them, so exhausted branches stop being explored at all. It is rarely necessary and it is a good thing to mention as a refinement.
Two techniques, one problem
This problem is the reason Tries follows Backtracking rather than sitting elsewhere in the course. Neither technique alone solves it: the backtracking explores the grid and the trie decides which explorations are worth doing.
Before starting, write down the grid search you already know, then add the trie node as a parameter and the child lookup as the first guard. Framed that way it is a modification rather than a new problem.
Cost of the naive approach
Running the single-word grid search once per word, for w words on an m by n grid, where each search explores up to four directions for up to L steps. What is the time, and what extra space does the trie version add?
Time
Space
Word Search Ii
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.