MEDIUM

Word Search

Given an m×n grid of characters board and a string word, return true if word can be formed by a path of sequentially adjacent cells (horizontally or vertically), where no single cell is reused within one word.

Example

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

Output true

Key Pointers

This is DFS with backtracking on a grid: try every cell as a potential start, and explore its 4 neighbors for the next matching letter.
Mark a cell visited by temporarily overwriting it (e.g. with "#") instead of a separate visited set — cheaper, and trivially undone on backtrack.
Do the bounds and letter-match check before recursing, so a failed match never enters the next call.

Step-by-Step Analysis

For each starting cell (r, c), call dfs(r, c, 0) — 0 is the index into word being matched.
In dfs: if the index equals len(word), the whole word matched — return True.
If (r, c) is out of bounds, or board[r][c] != word[index], return False.
Otherwise temporarily mark board[r][c] visited, recurse into all 4 neighbors with index + 1, restore board[r][c] afterward, and return True if any neighbor succeeded.
Return True as soon as any starting cell's dfs succeeds; otherwise False once every cell is exhausted.

Complexity

Time: O(m · n · 4^L) where L = len(word) — Space: O(L) recursion depth

Code

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 r < 0 or c < 0 or r >= rows 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
        return found

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

Code Explanation

How the solution above works, piece by piece.

Try every cell as a starting point.
dfs(r, c, i) checks whether word[i:] can be spelled starting at (r, c). If i == len(word), every letter matched.
Fail if the cell is off the board or its letter isn't word[i].
Mark the cell as # (visited), try all 4 neighbours for the next letter, then restore the letter. The or chain stops at the first success.
Worst case O(m · n · 4^L) for word length L; in practice the letter check prunes most branches.

Visual Walkthrough

Running it on the example board with word = "ABCCED":

The DFS starts at the top-left A and follows neighbouring cells letter by letter (numbered). Temporarily writing # into a visited cell stops the path from using the same cell twice.

matched path

Video Explanation

NeetCode — Backtracking, LeetCode 79