Word Search
Decide whether a word can be formed by adjacent board cells without reusing a cell.
Why does this pattern fit?
Restate the exact job
Decide whether a word can be formed by adjacent board cells without reusing a cell.
Each prefix determines the cell, next character, and temporarily unavailable path.
O(mn·4^L) time · O(L) stack
Failing to undo visited state blocks valid paths from other starts.
How to solve Word Search
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
Decide whether a word can be formed by adjacent board cells without reusing a cell.
Why Backtracking fits
Each prefix determines the cell, next character, and temporarily unavailable path.
State to maintain
Row, column, word index, and visited marking.
Transition
Match, mark, explore four neighbors, then restore the cell on return.
Time and space
O(mn·4^L) time · O(L) stack
Counterexample to the tempting mistake
Failing to undo visited state blocks valid paths from other starts.
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.