Word Search
Decide whether a word can be traced through horizontally or vertically adjacent grid cells, using each cell at most once.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Start a depth-first search from every cell that matches the first letter. Mark cells as visited on the way down and restore them when backtracking.
Pattern: Backtracking. Build a candidate one choice at a time and undo the choice when it cannot lead to a solution.
Complexity
| Measure | Bound |
|---|---|
| Time | O(m · n · 3^L) |
| Extra space | O(L) recursion depth |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.