Word Search

Problem

Optical character recognition engines verify extracted text against a character grid to confirm spatial coherence - the letters must be physically adjacent on the source document. Given an m x n grid of characters and a word, return true if the word exists in the grid. The word must be formed by sequentially adjacent cells (up, down, left, right); the same cell may not be used more than once.

Example 1:

Input: board = [["K","R","U","M"],
                ["A","P","E","O"],
                ["L","N","T","S"]], word = "PETS"
Output: True
Explanation: the path is P(1,1) -> E(1,2) -> T(2,2) -> S(2,3): right, down, right - each step adjacent, no cell reused.

Example 2:

Input: same board, word = "MOS"
Output: True
Explanation: M(0,3) -> O(1,3) -> S(2,3), straight down the last column.

Example 3:

Input: same board, word = "KUMK"
Output: False
Explanation: the only path back to K would reuse a cell, which is not allowed.

Constraints:

• 1 <= board.length, board[i].length <= 6
• 1 <= word.length <= 12
• board and word consist of only uppercase and lowercase English letters.

Solution Breakdown

Approach: DFS backtracking on a grid, marking visited cells in-place with a sentinel and restoring on return.

An outer double loop tries every cell as a possible start; the inner backtrack(r, c, index) walks one candidate path. The base case is index == len(word) - the whole word matched, return True. The guard r/c out of bounds or board[r][c] != word[index] returns False, pruning the entire subtree below a mismatch. The clever part is the visited mechanism: instead of a separate visited set, the cell is overwritten with '#' (a character that cannot appear in the word) so the four recursive neighbor calls cannot step back onto it within this path; after they return, board[r][c] = temp restores the original letter. That restore is what makes it backtracking rather than plain DFS - sibling branches and later starting cells must see the unmodified board. The neighbor recursion is wrapped in any(...), which short-circuits: the first neighbor that completes the word returns True and the rest are skipped. Trace "PETS" starting from P at (1,1): it walks right to E, down to T, right to S, and index reaches the word length - True. "KUMK" fails because the only way to revisit K is reusing a cell, which the sentinel forbids.

Edge cases: A length-1 word succeeds the instant a cell matches word[0], before any neighbor is explored. A first character absent from the grid fails every start and returns False.

Complexity: O(m * n * 4^L) time, O(L) space - each of m*n cells can launch a DFS branching 4 ways for L steps; the only extra space is the recursion stack of depth L (input mutated in place and restored).