Word Search LeetCode 79 — Backtracking

LeetCode 79 Word Search gives you an m x n grid of characters called board and a string word. Your task is to return true if word exists in the grid. The word must be constructed from letters of sequentially adjacent cells — horizontally or vertically neighboring cells only. The same cell cannot be used more than once in a single path.

This problem is a classic backtracking exercise on a 2D grid. Unlike dynamic programming problems, there is no optimal substructure to exploit — the answer depends on the full path, not just local state. You must explore all possible starting positions and all reachable directions from each step, pruning aggressively whenever the current cell does not match the expected character.

Understanding the constraints is key to choosing the right approach and estimating performance. The grid can be up to 6x6 in practice for timed LeetCode tests, but the algorithm must handle arbitrary sizes up to the constraint bounds.

The core approach is to iterate over every cell in the grid. When a cell contains word[0], launch a DFS from that cell. The DFS takes the current cell coordinates and the current index into word. At each step, it checks whether board[row][col] matches word[index]. If it does, it marks the cell visited, recurses into the four cardinal directions with index + 1, and then unmarks the cell on the way back up (backtracking).

Marking a cell as visited is essential to prevent reusing the same cell in a single path. If we visit cell (r, c) at step 3 and then revisit it at step 5 in the same DFS branch, we would be using the same physical cell twice — which the problem forbids. After the recursive call returns, we must restore the original character so that other DFS paths starting from different cells can still use this cell.

The DFS terminates successfully when index reaches word.length, meaning every character in word has been matched. It terminates unsuccessfully when the current cell is out of bounds, when the current character does not match word[index], or when the cell has already been marked visited in the current path.

The DFS helper function takes four arguments: the board, the current row and column, and the current index into word. The first thing to check is the base case: if index equals word.length, all characters have been matched and we return true immediately. This is the success condition.

Next, check failure conditions before doing any work: if row or col is out of bounds, return false; if board[row][col] does not equal word[index], return false. These two checks prune the search early. Only after both checks pass do we proceed to mark the cell and recurse.

Mark the cell by saving its original character and overwriting it with the sentinel. Then call the DFS in all four directions — up, down, left, right — with index + 1. If any direction returns true, propagate true upward immediately. Finally, restore the original character regardless of outcome. This restoration is the "backtrack" step that makes the algorithm correct.

Before launching any DFS, perform a character frequency check. Count how many times each character appears in word and how many times it appears in board. If word requires more of any character than the board contains, the word cannot possibly exist — return false immediately. This O(mn + L) check can eliminate the search entirely for impossible inputs.

A more subtle but powerful optimization involves comparing the frequency of the first and last characters of word. If the last character of word is rarer on the board than the first character, reverse word before searching. A reversed word represents the same path traversed in the opposite direction, so the answer is unchanged. The benefit is that DFS starting from rarer characters has far fewer starting points, dramatically reducing the branching factor.

These two optimizations do not change the worst-case complexity but can reduce practical runtime by orders of magnitude on boards where certain characters are scarce. In competitive programming and interview settings, these tricks demonstrate deep understanding of the problem structure beyond just implementing the basic DFS.

The worst-case time complexity is O(m * n * 4^L) where m and n are the board dimensions and L is the length of word. The outer loop visits each of the m*n cells as a potential starting point. From each starting cell, the DFS explores up to 4 directions at each of L steps. In the absolute worst case, no pruning occurs and the full 4^L tree is explored from every cell.

In practice, character mismatch pruning is extremely effective. Most cells will not match word[0] and are immediately skipped. Of those that match word[0], most paths will fail quickly at word[1] or word[2] due to character mismatches. The in-place visited marking also prevents the DFS from cycling, which bounds the actual search tree to L nodes deep with at most 3 directions at each step (cannot go back the way we came).

Space complexity is O(L) for the recursion call stack, where L is the word length. This is the only extra space used — the visited marking is done in-place in the board array itself. If you use a separate visited matrix instead of in-place marking, space becomes O(m * n + L).

Python solution: define exist(board, word) with nested backtrack(r, c, idx). Outer loop iterates over all (r, c) pairs; if backtrack(r, c, 0) returns True, return True immediately. The backtrack function: if idx == len(word), return True; if r or c out of bounds, return False; if board[r][c] != word[idx], return False. Save temp = board[r][c], set board[r][c] = '#'. Result = any of the four recursive calls. Restore board[r][c] = temp. Return result. O(mn * 4^L) time, O(L) space.

Java solution: public boolean exist(char[][] board, String word). Define private boolean backtrack(char[][] board, String word, int r, int c, int idx). Base case: if idx == word.length(), return true. Bounds check: if r < 0 || r >= board.length || c < 0 || c >= board[0].length, return false. Character check: if board[r][c] != word.charAt(idx), return false. char temp = board[r][c]; board[r][c] = '#'. boolean found = backtrack(r-1,c,idx+1) || backtrack(r+1,c,idx+1) || backtrack(r,c-1,idx+1) || backtrack(r,c+1,idx+1). board[r][c] = temp. Return found. The outer exist method iterates all cells and calls backtrack(board, word, r, c, 0).

Both solutions use identical logic. The key difference is that Java uses charAt and the || short-circuit operator naturally avoids unnecessary recursive calls once a true result is found. Python uses any() or chained or statements for the same effect. Both restore the cell character unconditionally after recursion, ensuring correctness across all branches.

Word Search II (LeetCode 212) is the natural extension: given a board and a list of words, find all words that exist in the board. The naive approach runs Word Search 79 once per word, but this is inefficient when the word list is large. The optimal solution builds a Trie from all words, then runs a single DFS over the board, pruning branches where no word in the Trie can match the current prefix. This reduces redundant exploration across words sharing prefixes.

N-Queens (LeetCode 51) shares the backtracking template: place a queen, mark the row/column/diagonal as attacked, recurse to the next row, unmark on backtrack. The structure is identical to Word Search — choose a position, mark it used, recurse, unmark. The key insight from Word Search that applies broadly is in-place marking: modifying the existing data structure rather than maintaining separate auxiliary state.

Number of Islands (LeetCode 200) uses DFS on a grid but without backtracking — cells are permanently marked because we want to count connected components, not find a specific path. The grid DFS family (Word Search, Number of Islands, Pacific Atlantic Water Flow, Surrounded Regions) all share the same directional recursion skeleton. Mastering Word Search backtracking gives you the foundation for all grid DFS problems.