Word Search – Solution & Complexity
Watch: Word Search with grid backtracking: mark, explore, unmark
Try every cell as a start and run a DFS that matches the word one letter at a time, up, down, left or right. Overwrite each matched cell with # while it's on the current path, so ABCB can't reuse its B, and write the letter back when the call returns, so a dead end doesn't block a later start. Walking greedily down one path misses answers that need a step back. Every path is m·n·4^L, but stopping at the first wrong letter cuts almost all of them. O(m·n·4^L) time in the worst case, O(L) recursion space.
Solution Walkthrough
Step 1: Recognize the Pattern
The key pattern is: DFS backtracks over matching adjacent cells. Identify the state and invariant before coding.
Step 2: Build the Algorithm
Advance one state transition at a time. Mark or update state before exploring dependent work.
Step 3: Check Edge Cases
Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.
Step 4: Solution and Complexity
Time: O(mn4^L). Space: O(L).