Word Search (Grid Backtracking)

Interview Prep

StandardBacktrackingbacktrackinggriddfs

The problem

Given a 2D grid of characters and a word, decide whether the word can be constructed by walking through adjacent cells (up, down, left, right — no diagonals), where each cell may be used at most once per path.

Pattern: DFS with in-place mark / restore

The standard grid backtracking template. From each starting cell matching word[0], run a DFS that consumes letters of the word as it walks. At each step: bounds check, character match check, mark the current cell visited, recurse into the four neighbors, then restore the cell before returning. The restore is critical — without it, sibling DFS calls would see the cell as still visited and miss valid paths.

Mutating the board in place is a common space-saving trick: no separate visited set is allocated. Use any sentinel character that can't appear in either the board or the word.

Solution

def exist(board: list[list[str]], word: str) -> bool:
    R, C = len(board), len(board[0])

    def dfs(r: int, c: int, k: int) -> bool:
        if k == len(word):
            return True
        if r < 0 or r >= R or c < 0 or c >= C or board[r][c] != word[k]:
            return False

        # Mark as visited (in place — restore on the way out)
        save = board[r][c]
        board[r][c] = '#'

        found = (dfs(r + 1, c, k + 1)
              or dfs(r - 1, c, k + 1)
              or dfs(r, c + 1, k + 1)
              or dfs(r, c - 1, k + 1))

        board[r][c] = save           # restore for sibling branches
        return found

    return any(dfs(r, c, 0) for r in range(R) for c in range(C))

Trace

board = [['A','B','C','E'],
         ['S','F','C','S'],
         ['A','D','E','E']]
word = "ABCCED"

Start dfs(0,0,k=0): board[0][0]='A' == 'A'. mark, recurse.
  dfs(1,0,1): 'S' != 'B'. fail.
  dfs(-1,0,1): out of bounds.
  dfs(0,1,1): 'B' == 'B'. mark, recurse.
    dfs(1,1,2): 'F' != 'C'. fail.
    dfs(-1,...): oob.
    dfs(0,2,2): 'C' == 'C'. mark, recurse.
      dfs(1,2,3): 'C' == 'C'. mark, recurse.
        dfs(2,2,4): 'E' == 'E'. mark, recurse.
          dfs(2,3,5): 'E' != 'D'. fail.
          dfs(2,1,5): 'D' == 'D'. mark, recurse.
            dfs(...,6) k==len(word) -> True!
          ...

return True

Complexity

Time: O(R · C · 3^L) worst case, where L is the word length. From any starting cell, the DFS branches at most 3-ways (we can't return to the cell we just came from), to depth L.
Space: O(L) recursion stack. No extra heap allocation thanks to the in-place mark.

Variations worth knowing

Word Search II (many words): the naive solution runs Word Search per word — far too slow when the dictionary is large. The correct answer builds a trie of all words, then DFS the board following trie edges. Each grid cell is visited only as long as some unfinished word in the trie is compatible; orders of magnitude faster.
Number of distinct paths spelling word: same DFS, but count branches instead of returning True at the first success.
Boggle: like Word Search II but with 8-neighbor moves (diagonals included). Same trie + DFS skeleton.
Longest path in grid with constraints: DFS with memoization when the grid has a partial order (e.g., values must strictly increase). With cycles allowed, it's NP-hard.