Word Search

Signal

Tracing a path through a grid that must match a sequence, without reusing a cell, is DFS-with-backtracking: explore a direction, and if it doesn't pan out, undo the "visited" mark and try the next one.

Approach

Try starting from every cell that matches the word's first letter. From there, DFS in the 4 directions, matching one letter deeper per call, while temporarily marking the current cell visited so the path can't double back on itself. If a branch fails, unmark the cell (backtrack) and try the next direction; if every direction fails, that starting cell fails too.

Skeleton

def dfs(r, c, i):
    if i == len(word): return True
    if out of bounds or board[r][c] != word[i]: return False
    temp, board[r][c] = board[r][c], marker
    found = any(dfs(r+dr, c+dc, i+1) for dr, dc in dirs)
    board[r][c] = temp
    return found

Solution

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

    def dfs(r: int, c: int, i: int) -> bool:
        if i == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
            return False

        temp = 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] = temp
        return found

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

Complexity

O(rows · cols · 4^L) time in the worst case, where L is the word length — up to 4 branches at each of L steps, tried from every starting cell. O(L) space for the recursion stack.

Pitfalls

• Using a separate visited set instead of mutating the board in place — both work, but forgetting to restore the board (board[r][c] = temp) after a failed branch corrupts later searches from other starting cells.
• Checking the letter match before the bounds check — indexing board[r][c] before confirming r, c are in range throws instead of failing cleanly.
• Relying on or's short-circuiting across the four directions is correct and idiomatic here — rewriting it as four separate if blocks without an early return True just re-explores unnecessarily.