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.

Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]], word = "ABCCED"
Output: True
 
Input: same board, word = "SEE"
Output: True
 
Input: same board, word = "ABCB"
Output: False

Solution

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 "ABCCED" from the top-left A: it walks right to B, C, down to the second C, down/across to E, D, matching adjacent cells, and index reaches the word length - True. "ABCB" fails because the only way to revisit B 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).