LeetCode 79: Word Search — Step-by-Step Visual Trace

#python #leetcode #algorithms

Medium — Backtracking | Depth-First Search | Matrix | String

The Problem

Given a 2D board of characters and a target word, determine if the word exists in the grid by connecting adjacent cells horizontally or vertically.

Approach

Use backtracking with depth-first search to explore all possible paths from each starting position. Mark visited cells temporarily to avoid revisiting, then backtrack by restoring the original character.

Time: O(m * n * 4^L) · Space: O(L)

Code

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(row, col, index):
            if index == len(word):
                return True

            if (
                row < 0
                or row >= len(board)
                or col < 0
                or col >= len(board[0])
                or board[row][col] != word[index]
            ):
                return False

            original_char = board[row][col]
            board[row][col] = "#"  # Mark the cell as visited

            found = (
                dfs(row + 1, col, index + 1)
                or dfs(row - 1, col, index + 1)
                or dfs(row, col + 1, index + 1)
                or dfs(row, col - 1, index + 1)
            )

            board[row][col] = original_char  # Backtrack

            return found

        for row in range(len(board)):
            for col in range(len(board[0])):
                if board[row][col] == word[0] and dfs(row, col, 0):
                    return True

        return False