AlgoScope

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, algorithm, intermediate
Extend right to 0, 1.0123012abcesfcsadee
Extend right to 0, 1.0123012abcesfcsadee

Backtracking: Word search with a dead end

Decision, step 3 of 9

At (0,0) with "a" matched, the next letter is 'b'. Free neighbours: down 's', right 'b'. Go right to (0,1).

How backtracking works

Cost

Best
O(r * c)
Average
O(r * c * 3^L)
Worst
O(r * c * 3^L)
Space
O(L)

Taught by the same lesson

Backtracking covers these too, in the same run.