Word Search

Try starting the search from every cell that matches word[0], then DFS outward matching one character at a time — backtracking (un-visiting a cell) whenever a path dead-ends, since that same cell may be needed by a different path.

DFS with a Separate Visited Set

Time O(m·n·4^L)Space O(L)

From each starting cell, recursively try all four directions, tracking visited cells in a separate set so the same cell is not reused within one attempt.

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

        def dfs(r, c, i):
            if i == len(word):
                return True
            if (
                r < 0 or r >= rows or c < 0 or c >= cols
                or (r, c) in visited or board[r][c] != word[i]
            ):
                return False
            visited.add((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)
            )
            visited.remove((r, c))
            return found

        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True
        return False

Correct, but the visited set is an extra O(L) structure (and a hash-set membership check per cell) on top of the grid we already have.

DFS with In-Place Marking

OptimalTime O(m·n·4^L)Space O(L)

Instead of a separate set, temporarily overwrite the current cell with a sentinel character (one that can never match a letter) while it is part of the in-progress path, then restore it — the same “mark and undo” backtracking idea, without allocating another data structure.

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        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
            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  # backtrack: restore the cell for other paths
            return found

        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True
        return False

Tracing word = "ABCB" (the statement’s false example) on the same board. Watch the board characters themselves: a cell on the live path is overwritten with #, and the instant a branch dead-ends that cell is restored to its letter so a later path can use it again.

Board — # is a cell on the live path

searching

Word — matched 0 / 4

ABCB

Current path

empty — no cell is marked

1 / 10

currentresultdiscarded

Scan every cell for word[0] = A. Every match starts a DFS, and marks go directly on the board instead of into a visited set.

After the branch through (0,2) fails, the DFS restores it to C and backs up to (0,1). Finding no untried neighbor there, it restores (0,1) too, then finally restores (0,0) — the whole failed path is unwound so the scan can start fresh at the next A, (2,0). That discard-and-retry pattern is what backtracking relies on here.

Why it is correct: marking a cell with a sentinel prevents the current path from revisiting it, and restoring it on the way back out means the same cell remains available to a different path that does not go through this position. Complexity: there are m·n starting cells, and each DFS branches into up to 4 directions for each of the L = len(word) characters → O(m·n·4^L) time worst case (mitigated in practice by the immediate character mismatch check). The recursion depth is at most L → O(L) space, with no separate visited structure.

DFS with a Separate Visited Set

DFS with In-Place Marking

More Backtracking practice