Word Search

Intuition

Every occurrence of the word must begin at some cell whose character matches the first letter, so we launch a search from each cell. From a matching cell we attempt to extend the match into any of the four orthogonal neighbors for the next letter. To respect the no-reuse rule we overwrite the current cell with a placeholder before recursing and restore it afterward, which acts as an on-the-fly visited set without extra memory. A branch succeeds the moment the entire word has been matched.

Algorithm walkthrough

1. 1Loop over every cell and start a search whenever it could match the first character.
2. 2In the search, if the matched length equals the word length, report success.
3. 3If the position is out of bounds or the character does not match the expected letter, fail this branch.
4. 4Mark the current cell with a placeholder, then search up, down, left, and right for the next letter.
5. 5Restore the original character before returning so other paths can reuse the cell.

Implementation

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])

        def backtrack(r: int, c: int, index: int) -> bool:
            if index == len(word):
                return True
            if (r < 0 or r >= rows or c < 0 or c >= cols
                    or board[r][c] != word[index]):
                return False
            temp = board[r][c]
            board[r][c] = "#"
            found = (
                backtrack(r + 1, c, index + 1)
                or backtrack(r - 1, c, index + 1)
                or backtrack(r, c + 1, index + 1)
                or backtrack(r, c - 1, index + 1)
            )
            board[r][c] = temp
            return found

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