View on NeetCode
View on LeetCode

Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Solution

Approach: DFS Backtracking

The key insight is to try starting from each cell, then use DFS to explore all 4 directions while marking visited cells.

Implementation

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        def dfs(r, c, index):
            # Found complete word
            if index == len(word):
                return True

            # Check bounds and character match
            if (r < 0 or r >= m or c < 0 or c >= n or
                board[r][c] != word[index]):
                return False

            # Mark as visited
            temp = board[r][c]
            board[r][c] = '#'

            # Explore 4 directions
            found = (dfs(r + 1, c, index + 1) or
                     dfs(r - 1, c, index + 1) or
                     dfs(r, c + 1, index + 1) or
                     dfs(r, c - 1, index + 1))

            # Restore cell
            board[r][c] = temp

            return found

        # Try starting from each cell
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True

        return False

Complexity Analysis

• Time Complexity: O(m * n * 4^L), where m*n is board size and L is word length. We try 4 directions up to L depth from each cell.
• Space Complexity: O(L) for recursion depth.

Key Insights

1. Try All Starting Points: We try starting the search from every cell on the board.

2. In-Place Marking: We mark visited cells by modifying the board itself (using ‘#’), saving space over a separate visited set.

3. Backtracking: After exploring, we restore the cell value so other paths can use it.

4. Short-Circuit OR: Using or allows us to return true immediately when any direction succeeds.

5. Early Termination: If we find the word from any starting position, we can return true immediately.