Word Search · DSA Prep

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 = "ABCCED" on the example board — the DFS commits to a path, and when the last two letters (“E”,“D”) force a dead end it backtracks and tries an alternative “C”:

1 / 6

landwatervisitedcurrent

Start at (0,0) = A, matching word[0] = A. Mark it visited and search neighbors for B.

If the board instead had no D adjacent to the final E, the DFS would restore (2,2) back to E, back up to (1,2), and retry the other neighboring C (at (1,1)) before giving up on this branch entirely — exactly the discard-and-retry pattern backtracking relies on.

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.