Word Search

Word Search asks you to trace a word through a grid of letters, stepping only between side-by-side cells and never reusing a cell. It is the classic introduction to DFS with backtracking on a 2D board — the move that powers mazes, flood fills, and constraint puzzles.

A B C E
S F C S
A D E E

The slow way first

You might try to enumerate every possible path through the grid and check each one against the word. But the number of paths explodes combinatorially — there is no clean way to list them all without walking the grid anyway. The real question is: standing on a cell that matches the next letter, where can I go? That nudge — explore one neighbor as far as it goes, and rewind if it fails — is exactly depth-first search with backtracking.

The idea: walk, mark, and rewind

Start a DFS from every cell. At each cell, check whether it matches the letter we still need (word[i]). If it does, mark it visited so the path cannot loop back onto it, then recurse into its four neighbors looking for word[i+1]. If a branch dead-ends, unmark the cell (backtrack) so a different path is free to use it later. The moment i reaches the end of the word, we have spelled the whole thing.

The mark/unmark pair is the heart of backtracking: a cell is off-limits only while it sits on the current path.

Walk through it

Step through the animation. The dfs pointer walks from A at the top-left, matching A → B → C. From that first C it first tries the neighbor E, which is not the C we need — a dead-end, so it unmarks that cell and steps back. It then takes the other C going down, reaches E, and finally D, completing "ABCCED". That one backtrack is the whole lesson.

Pseudocode

dfs(r, c, i):
    if i == length of word:          # matched every letter
        return True
    if out of bounds, or board[r][c] != word[i]:
        return False                 # this branch fails
    remember board[r][c], then mark it visited
    try dfs into all 4 neighbors with i + 1
    restore board[r][c]              # backtrack: unmark
    return whether any neighbor succeeded
 
for each starting cell (r, c):
    if dfs(r, c, 0): return True
return False

The Python solution

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):
            return True
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or board[r][c] != word[i]):
            return False
        tmp = board[r][c]
        board[r][c] = "#"
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        board[r][c] = tmp
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

• dfs(r, c, i) asks: can I spell word[i:] starting at cell (r, c)?
• The first if is the success base case — once i equals the word length, every letter is placed.
• The second if is the failure base case — off the board, or the letter does not match what we need.
• board[r][c] = "#" is the mark: a sentinel that can never equal a real letter, so the path cannot reuse this cell.
• Line 13, board[r][c] = tmp, is the backtrack — it restores the letter so other paths are free to step here.
• The outer loops try the search from every cell, since the word could start anywhere.

Complexity

The branching factor is 4 (down to 3 after the first step, since we never go back the way we came), and the depth is the word length L, so a single search is O(4^L). We launch it from up to m·n cells. The extra space is just the recursion stack, at most L deep.

When this pattern shows up

Practice