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.
Backtracking: 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).
Cost
- Best
- O(r * c)
- Average
- O(r * c * 3^L)
- Worst
- O(r * c * 3^L)
- Space
- O(L)
Before this
Taught by the same lesson
Backtracking covers these too, in the same run.