Q77: Word Search in Grid. - DSA Patterns (Multi-Lang)

In Simple Words: DFS from every matching starting cell in 4 directions. In-place marker: temporarily replace cell with # to mark visited, and restore original character on backtrack.

Time: $O(M \cdot N \cdot 4^L)$ | Space: $O(L)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word): return True
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[i]:
            return False
        tmp = board[r][c]
        board[r][c] = "#"
        res = (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 res

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