Word Search

Given a 2-D grid of characters board and a string word, return true if the word is present in the grid, otherwise return false.

For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Approach

Use DFS backtracking from each cell. At each step, match the next character, mark the cell as visited, and recurse to neighbors. Restore the cell after recursion so other paths can reuse it. If all characters are matched, return true.

Why It Works

A word exists in the grid iff there is a path of adjacent cells matching its characters in order without reuse. DFS explores all such paths from each starting cell, and backtracking ensures the grid state is correct for other paths. Therefore it returns true exactly when a valid path exists.

Complexity

• Time: O(m * n * 4^L) worst-case, where L is word length
• Space: O(L) for recursion

Reference Implementation (Python)

class Solution:
    def exist(self, 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:
                return False
            if board[r][c] != word[i]:
                return False

            tmp = 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] = tmp
            return found

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