Word Search
The problem
Determine whether a nonempty word can be traced in a rectangular character board by horizontal or vertical moves, without using a cell twice in that path.
Example
board = [["s", "e"], ["a", "t"]], word = "set" → true
Need a hint?
A visited mark belongs to the current path, not to the entire search.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Try each cell as a starting point. Reject a mismatched character or an already used cell. Mark the cell, explore neighbors for the next character, and unmark it before returning, including on success. Reaching the last matching character succeeds.
Complexity
O(mn·4·3^(L−1)) loose worst-case time and O(L) path space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.