Start with one word#
Finding a single word in a grid of letters is a depth first search. From each cell that matches the first letter, walk to neighbours matching the next letter, marking cells as used so a path cannot cross itself, and unmarking them as you back out. That unmarking is what makes it backtracking rather than plain search: the state is restored so the next branch starts clean.
Why repeating that is the wrong move#
With 1000 words you could run that search 1000 times. It works and it is far too slow, because the same prefixes get walked again and again. "cat", "car" and "care" all begin with "ca", and each search rediscovers it.
Turn the dictionary inside out#
A trie stores the words as a tree of characters. Shared prefixes share nodes, and each node knows whether a word ends there.
Now walk the grid once, carrying a trie node alongside your position. Move to a neighbour only if the trie node has a child for that letter. If the node has no such child, there is no word in the entire dictionary that continues this way, and the branch dies immediately. That single check is what turns a thousand searches into one.
When you reach a node marked as the end of a word, record it.
Pruning is what makes it fast#
Two prunings matter more than anything else:
- Remove a word from the trie once you have found it. Otherwise the same word is found by many paths and you have to deduplicate later.
- Delete leaf nodes on the way out. Once a node has no children and no word, no future path through it can succeed. The trie shrinks as the search runs, and late branches die instantly.
Without those, the algorithm is correct and slow. With them it is fast on inputs that look hostile.
The cost#
Building the trie is O(total characters). The search is bounded by the grid size times the branching, but in practice the trie prunes almost everything, which is exactly why the technique exists.
Common mistakes#
- Forgetting to unmark a visited cell when backing out, which makes later branches see a grid full of holes.
- Collecting duplicates because a word is reachable by several paths.
- Storing whole strings on every node instead of a flag plus the word at its end.