Word Search II
Return all dictionary words present in a board without reusing cells.
Why does this pattern fit?
Restate the exact job
Return all dictionary words present in a board without reusing cells.
A trie shares prefix work across many words and prunes impossible paths.
O(mn·4^L) worst-case · O(dictionary characters) space
Running a separate board search for every word repeats prefixes.
How to solve Word Search II
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Return all dictionary words present in a board without reusing cells.
Why Tries & prefix search fits
A trie shares prefix work across many words and prunes impossible paths.
State to maintain
Board position, trie node, visited mark, and found-word marker.
Transition
Advance the trie with the cell, emit terminal words once, explore neighbors, and prune dead trie branches.
Time and space
O(mn·4^L) worst-case · O(dictionary characters) space
Counterexample to the tempting mistake
Running a separate board search for every word repeats prefixes.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.