Trace a word through a letter grid

Start a depth-first search from every cell that matches the first letter. At each step, mark the cell used, try the four neighbours for the next letter, then unmark it. A branch stops as soon as a letter does not match. Worst case O(R · C · 3^L) for a word of length L, since each step has at most three unused directions. The recursion and the used set take O(L) space.

Mark and unmark on the way in and out: that is the backtracking part.

Quick rejects: the word is longer than the grid, or the grid lacks enough of some letter.

Searching from the rarer end of the word can cut the work a lot.

STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def can_trace(grid: list[str], word: str) -> bool:
    used: set[tuple[int, int]] = set()

    def follow(y: int, x: int, done: int) -> bool:
        if done == len(word):  # every letter matched
            return True
        if not (0 <= y < len(grid) and 0 <= x < len(grid[0])):
            return False
        if (y, x) in used or grid[y][x] != word[done]:
            return False
        used.add((y, x))  # on the current path
        found = any(follow(y + dy, x + dx, done + 1)
                    for dy, dx in STEPS)
        used.discard((y, x))  # free it for other paths
        return found

    return any(follow(y, x, 0) for y, row in enumerate(grid)
               for x in range(len(row)))

Common mistakes

• Forgetting to unmark, which blocks cells for other paths.
• Allowing a cell to be reused.

Mention the letter-count reject; it shows practical sense.

Follow-up questions

Think of your answer first, then open the hint.

1. How do you search for many words at once?

   Show hint

   Put the words in a trie and walk the trie alongside the grid search.

2. Why 3^L and not 4^L?

   Show hint

   After the first step, the cell you came from is already used.