Introduction

In programming problems, a word search algorithm usually means checking whether a target word can be formed inside a character grid. The common rule set is simple: start at any cell, move to adjacent cells, and do not reuse the same cell in one path.

The problem looks small, but it is a good example of state exploration, pruning, and backtracking. Once you understand the recursive structure, the same pattern shows up in path finding, puzzle solvers, and constraint search.

Modeling the Search Space

Assume the board is a two-dimensional array of characters and the word is a string. A valid solution needs three pieces of state:

• The current row
• The current column
• The index of the next character to match

At each step, the algorithm asks one question: does the current cell match word[index]? If the answer is no, the path stops immediately. If the answer is yes, the search continues into neighboring cells for the next character.

This is why depth-first search fits well. A partial match either grows into a full match or fails and returns control to the previous step.

Depth-First Search with Backtracking

The standard approach is:

1. Loop over every cell as a possible starting point.
2. Run a recursive search from that cell.
3. Mark the cell as visited while exploring that path.
4. Restore the cell when the recursive call returns.

Here is a runnable Python implementation:

1from typing import List
2
3
4def exist(board: List[List[str]], word: str) -> bool:
5    if not board or not board[0]:
6        return False
7
8    rows = len(board)
9    cols = len(board[0])
10
11    def dfs(row: int, col: int, index: int) -> bool:
12        if index == len(word):
13            return True
14
15        if row < 0 or row >= rows or col < 0 or col >= cols:
16            return False
17
18        if board[row][col] != word[index]:
19            return False
20
21        current = board[row][col]
22        board[row][col] = "#"
23
24        found = (
25            dfs(row + 1, col, index + 1)
26            or dfs(row - 1, col, index + 1)
27            or dfs(row, col + 1, index + 1)
28            or dfs(row, col - 1, index + 1)
29        )
30
31        board[row][col] = current
32        return found
33
34    for row in range(rows):
35        for col in range(cols):
36            if dfs(row, col, 0):
37                return True
38
39    return False
40
41
42grid = [
43    ["A", "B", "C", "E"],
44    ["S", "F", "C", "S"],
45    ["A", "D", "E", "E"],
46]
47
48print(exist(grid, "ABCCED"))  # True
49print(exist(grid, "SEE"))     # True
50print(exist(grid, "ABCB"))    # False

The important detail is the temporary marker "#". It prevents the same cell from being reused in a single path. After all recursive calls return, the original character is restored so that other starting paths can use the cell.

Why Backtracking Works

Backtracking is not a separate algorithm from depth-first search here. It is the cleanup step that makes recursive search correct. Each call assumes ownership of one cell, tries all allowed moves, and then puts the board back into its previous state.

Without restoration, later paths would read stale state and fail incorrectly. With restoration, every path sees a clean board except for the cells already used in that exact path.

The worst-case time complexity is exponential in the length of the word because each character can branch into several directions. A common estimate is O(rows * cols * 4^L), where L is the word length. In practice, mismatches prune the search quickly, so real performance is often much better than the worst case.

Optimizing for Many Words

If you need to search for one word, the plain backtracking solution is enough. If you need to search for many words on the same board, the problem changes. Running the same search repeatedly wastes work because prefixes overlap.

That is where a trie becomes useful. You build a prefix tree from all target words and traverse the board once while walking the trie at the same time. This allows you to stop early when no word shares the current prefix.

1words = ["SEE", "SEED", "ABCCED", "ABFS"]
2
3# A trie-based solution is more efficient here than calling exist
4# once per word because prefixes like "SE" are shared.

The underlying idea is still backtracking, but the trie reduces repeated prefix checks.

Common Pitfalls

One common mistake is forgetting to restore the visited cell after recursion. That causes later paths to behave as if the board has been permanently modified.

Another mistake is tracking visited cells with a copied set on every recursive call. That works, but it creates avoidable overhead. In-place marking is usually faster and simpler as long as restoration is done correctly.

Bounds checking also trips people up. The out-of-range check must happen before reading board[row][col], otherwise the code can crash on edge cells.

Finally, be careful with the base case. Returning True when index == len(word) means every character has already matched. If you place that check too late, you may reject valid solutions by one step.

Summary

• Word search on a grid is naturally solved with depth-first search plus backtracking.
• The recursive state is row, column, and character index.
• Marking a cell as visited and restoring it afterward is what keeps each path isolated.
• The single-word solution is simple and effective, while trie-based search is better for many words.
• Most bugs come from incorrect restoration, misplaced bounds checks, or off-by-one base cases.