Word Search in a Character Grid

1. Step 1: Initialize Solution.exist

   Replace the empty starter with the first real state owned by Solution.exist. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Assemble the primary transition

   Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.

3. Step 3: Pass the Path Exists case

   Complete the readable core algorithm for one representative Interview case. Run DFS from each possible start while marking and restoring cells in the current path.

4. Step 4: Harden the Cell Reuse Forbidden boundary

   Repair the reviewed boundary and pass the complete submission contract. The DFS index equals the number of matched characters. Marking prevents repeated cells on the active path, restoration preserves other paths, and exploring every start and neighbor sequence finds exactly the legal spellings.

• Visited state belongs to one path; restore the cell before returning to explore another start.
• recursion and backtracking
• trees and graphs

• LeetCode 79 — Word Search
• Hello Interview — Backtracking Overview

• Complete One Backtracking Frame(opens in a new tab)

  Complete One Backtracking Frame isolates before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element. That focused state discipline is required when implementing word search as a complete Interview Problem.

• Visit Each Grid Component(opens in a new tab)

  Visit Each Grid Component isolates a cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. That focused state discipline is required when implementing word search as a complete Interview Problem.

Start DFS at every cell; match one character, temporarily mark the cell, explore four neighbors, then restore it.

Why it works: The DFS index equals the number of matched characters. Marking prevents repeated cells on the active path, restoration preserves other paths, and exploring every start and neighbor sequence finds exactly the legal spellings.

class Solution:
    def exist(self, board, word):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        rows = len(board)
        columns = len(board[0])
        def search(row, column, index):
            if index == len(word):
                return True
            outside = not (0 <= row < rows and 0 <= column < columns)
            if outside or board[row][column] != word[index]:
                return False
            value = board[row][column]
            board[row][column] = None
            found = (
                search(row + 1, column, index + 1)
                or search(row - 1, column, index + 1)
                or search(row, column + 1, index + 1)
                or search(row, column - 1, index + 1)
            )
            board[row][column] = value
            return found
        return any(
            search(row, column, 0)
            for row in range(rows)
            for column in range(columns)
        )