Word Search in a Grid: Backtracking With Pruning, Step by Step

Word search is the backtracking problem that looks like a graph problem. A grid of letters, a word, and the question: can the word be spelled by walking between neighbouring cells, never using a cell twice? The search itself is a depth-first walk. What makes it an interview question is the two details that keep it correct and fast: the cell you are standing on must be blocked while you explore from it and released afterwards, and a wrong letter must end a branch immediately. This article covers both and checks the result against a brute force that walks every path.

The problem it solves

Given an m × n grid of letters and a word, return whether the word exists in the grid. Consecutive letters must sit in horizontally or vertically adjacent cells, and one cell may be used at most once in the word.

On the grid

s n a / b a k / t p o

"snap" exists: s at the top left, n to its right, the a below the n, and the p below that. "snip" does not: there is no i anywhere.

The naive picture is enormous: every path of length L from every cell. Pruning means most of those paths are never walked past their first wrong letter.

The intuition

Backtracking is choose, explore, un-choose. Here:

• Choose: the current cell matches word[k]. Mark it as used, for example by overwriting it with #.
• Explore: try the four neighbours for word[k + 1].
• Un-choose: put the letter back before returning.

The un-choose step is not tidiness. A cell that is wrong for one path can be exactly right for another: in the example, the first a tried is a dead end, and the search then needs the other a. If the first attempt left its cells blocked, later attempts would see a board with holes in it and could miss the word.

Pruning is the check at the top of every call: if the cell is off the board, already used, or holds the wrong letter, return at once. A whole subtree of paths dies on one comparison. That is the difference between a search that finishes and one that visits every path.

Two cheap checks before the search prune even more:

• Letter counts. If the word needs three as and the grid has two, answer no without searching. This is the classic defence against a grid full of a and a word like aaaaaab.
• Search from the rarer end. If the last letter of the word is rarer in the grid than the first, search for the reversed word: fewer starting cells, fewer branches.

Watch it run

The animation spells "snap" on the lesson's grid. Only one cell holds s, so the search has a single start, and it is marked as used. The next letter is n: of the two neighbours, only the one to the right matches, and the other dies on one comparison. Next comes a, and this time two neighbours match; the search takes the first, the top-right a, and remembers the other. From there the only unused neighbour is k, not p: a dead end, pruned. The search un-chooses that cell, its marker comes off, and it takes the other a, one row down. p sits directly below it, and the word is found. Every wrong branch cost one letter comparison; that is what keeps a board of nine cells from becoming thousands of routes.

The code

The lesson's search on any grid, with the letter-count check, and a counter of how many calls the search makes:

from collections import Counter

calls = 0

def exist(board, word):
    global calls
    rows, cols = len(board), len(board[0])
    if Counter(word) - Counter(ch for row in board for ch in row):
        return False                           # the grid lacks some letter: no search at all

    def dfs(r, c, k):
        global calls
        calls += 1
        if k == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[k]:
            return False                       # off the board, used, or the wrong letter
        board[r][c] = "#"                      # choose: blocked for this path only
        found = any(dfs(r + dr, c + dc, k + 1)
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[r][c] = word[k]                  # un-choose
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

grid = [list("sna"), list("bak"), list("tpo")]
print(exist(grid, "snap"), exist(grid, "snip"), exist(grid, "nap"))   # True False True
print(exist(grid, "kaka"), exist([list("ab"), list("cd")], "abdc"))   # False True
print(grid == [list("sna"), list("bak"), list("tpo")])                # True

The last line checks that the board is restored. Next, what the pruning buys: an all-a board and a word that almost fits. With the count check the answer is immediate; without it, the search walks a huge number of partial paths first:

calls = 0
print(exist([["a"] * 4 for _ in range(4)], "aaaaaaab"), calls)       # False 0

def exist_without_count_check(board, word):
    global calls
    rows, cols = len(board), len(board[0])
    def dfs(r, c, k):
        global calls
        calls += 1
        if k == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[k]:
            return False
        board[r][c] = "#"
        found = any(dfs(r + dr, c + dc, k + 1)
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[r][c] = word[k]
        return found
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

calls = 0
print(exist_without_count_check([["a"] * 4 for _ in range(4)], "aaaaaaab"), calls)   # False 11536

A brute force that lists every simple path of the right length, with no pruning at all, against the search on 1,000 random small grids:

import random

def brute(board, word):
    rows, cols = len(board), len(board[0])
    def paths(path):
        if len(path) == len(word):
            yield path
            return
        r, c = path[-1]
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in path:
                yield from paths(path + [(nr, nc)])
    return any("".join(board[r][c] for r, c in p) == word
               for r in range(rows) for c in range(cols) for p in paths([(r, c)]))

random.seed(17)
ok = True
for _ in range(1000):
    rows, cols = random.randint(1, 3), random.randint(1, 3)
    board = [[random.choice("ab") for _ in range(cols)] for _ in range(rows)]
    word = "".join(random.choice("ab") for _ in range(random.randint(1, 5)))
    ok &= exist([row[:] for row in board], word) == brute(board, word)
print(ok)                                      # True

The complexity

For an m × n grid and a word of length L:

• Time: O(m · n · 4 · 3^(L - 1)) in the worst case. Every cell can start a path; the first step has up to four neighbours and every later step at most three, since the cell you came from is blocked.
• Space: O(L) for the recursion, with no separate visited set, because the board itself carries the marks.
• Pruning does not change the worst case, but on real grids it cuts almost every branch after one or two letters.

Where it goes wrong

• Not restoring the cell. Later paths see holes in the board and can miss the word. The final check in the code catches this.
• One shared visited set that is never cleared. The same bug in another form: visited must mean "on the current path", not "ever touched".
• Checking the neighbour before recursing and the cell again inside. Harmless but double work; pick one place for the check.
• Moving diagonally. Only four directions count unless the problem says otherwise.
• Searching for many words one by one. For a list of words, build a trie and walk the grid once; that is word search II.

When it shows up in interviews

It is a standard medium and a common first backtracking question on a grid. Interviewers look for the choose, explore, un-choose shape, an honest complexity bound, and whether you restore the board. The usual follow-up is word search II, many words at once, where a trie replaces the single word and prunes on prefixes instead of letters. The same grid walk with marks appears in counting islands and flood fill, but there the marks are never removed, because those problems ask which cells are connected, not which paths exist.

How to say it in an interview

"I start a depth-first search from every cell that matches the first letter. In each call I return false if the cell is off the board, already used, or the wrong letter; that single check prunes the whole subtree. Otherwise I mark the cell, try the four neighbours for the next letter, and restore the cell on the way out, so other paths can still use it. Worst case is m · n · 4 · 3^(L - 1) with O(L) stack. Before searching I compare letter counts, which rejects impossible words instantly."

The idea of a search tree with branches cut early is the subject of backtracking vs dynamic programming, and the many-words version is in word search with a trie.