Word Search
DFS from each cell holding the first letter, extending through neighbours that hold the next one; cells on the path are used once.
Decision · step 3 of 9Backtracking: Word search with a dead end
At (0,0) with "a" matched, the next letter is 'b'. Free neighbours: down 's', right 'b'. Go right to (0,1).
What you will see
The path spells the word across the grid; mismatched neighbours are skipped.
Cost
| Best | O(r * c) |
|---|---|
| Average | O(r * c * 3^L) |
| Worst | O(r * c * 3^L) |
| Space | O(L) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Each node of the decision tree announces the choice made and whether it led to success, failure or further choices.
Reduced motion: Tree nodes appear and grey out in place; no travelling focus.
Before this
Taught by the same lesson
Backtracking covers these too, in the same run.