25. Find Pattern in KB Grid

Problem

KB content gets indexed into a 2D grid of short tokens for a structured-content matching experiment. Given a target word, check whether it can be traced as a path of adjacent (up/down/left/right, no cell reused) cells that spell it out end to end — a toy stand-in for pattern matching over structured content.

Grid cells are single characters. Return True if the word can be traced as a path of adjacent cells with no cell reused within the same path, and False otherwise.

Source: src/25_find_pattern_in_kb_grid.py

def exists(grid: list[list[str]], word: str) -> bool:
    ...

>>> grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
>>> exists(grid, "ABCCED")
True

>>> exists(grid, "SEE")
True

>>> exists(grid, "ABCB")
False

Step-by-Step Approach

1. Handle the trivial case: an empty word is trivially found (return True).
2. Write a recursive dfs(r, c, i) that asks: "can the remaining suffix word[i:] be traced starting from cell (r, c)?"
3. Base case for success: if i == len(word), every character has already been matched, so return True.
4. Base cases for failure: if (r, c) is out of bounds, or grid[r][c] != word[i] (this cell doesn't hold the character we need next), return False.
5. Otherwise the current cell matches. Temporarily mark it as visited (e.g. overwrite it with a sentinel like "#" that can't match any real letter) so the same path can't reuse it, then recursively try all four neighbors for i + 1.
6. After trying all four directions, restore the cell's original character before returning — this "undo" step is what makes it backtracking: the cell is only off-limits for paths that currently include it, not for paths explored later from a different start.
7. Try starting the search from every cell in the grid; if any start succeeds, the word exists.

The key insight is the mark-then-unmark (backtrack) step: without restoring the cell after exploring it, a failed path would permanently corrupt the grid for every subsequent search attempt from other starting cells.

Reference solution

def exists(grid: list[list[str]], word: str) -> bool:
    # backtracking DFS, marking visited cells in place; O(rows*cols*4^len(word)) worst case
    if not word:
        return True
    rows, cols = len(grid), len(grid[0]) if grid else 0

    # closure: reads grid/word/rows/cols from enclosing scope
    def dfs(r: int, c: int, i: int) -> bool:
        # success: every char of word already matched
        if i == len(word):
            return True
        # bounds short-circuits before indexing
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != word[i]:
            return False
        saved = grid[r][c]
        # mark visited in place, no separate visited set needed
        grid[r][c] = "#"
        # or short-circuits on first True
        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)
        # unmark/backtrack, run unconditionally
        grid[r][c] = saved
        return found

    # try every start cell, short-circuit on first hit
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Key Functions & Tricks

• def dfs(r, c, i) -> bool: — nested closure, reuses enclosing scope's grid/word/rows/cols.
• i == len(word) — success base case: every character of word matched.
• r < 0 or ... or grid[r][c] != word[i] — combined bounds + content guard, short-circuit safe.
• saved = grid[r][c]; grid[r][c] = "#" — mark step: sentinel excludes cell from reuse in this path.
• dfs(...) or dfs(...) or dfs(...) or dfs(...) — tries all four directions, short-circuits on first True.
• grid[r][c] = saved — unmark/backtrack, unconditional, prevents permanently corrupting the grid.
• any(dfs(r, c, 0) for r in range(rows) for c in range(cols)) — tries every start cell, short-circuits.

How to Recognize This Pattern