Word Search

Backtracking2D Matrix

30 min

Problem Statement

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

Example 1:

word = "ABCCED"

Output: true

Solution

This problem is a classic backtracking exercise. We need to search the grid for the first letter of the word. Once found, we can start a Depth-First Search (DFS) from that cell to see if we can form the rest of the word by moving to adjacent cells.

A key part of the backtracking approach is to keep track of visited cells for the current path to ensure we don't use the same letter twice. We can do this by modifying the board in-place (e.g., changing the character to a special marker like '#') before the recursive calls and changing it back after they return.

Algorithm Steps (Backtracking/DFS)

Iterate through each cell of the board to find a starting point.
If `board[r][c]` matches the first letter of the `word`, start a DFS from this cell.
The DFS function will check:
Base Case: If the word index reaches the end, we've found the word. Return `true`.
Boundary/Invalid Checks: Return `false` if out of bounds, or if the current cell doesn't match the word character.
Mark the current cell as visited.
Recursively call DFS on all 4 neighbors for the next character in the word. If any call returns `true`, we've found a path.
Backtrack: Un-mark the current cell so it can be used in other paths.
If any initial DFS call returns `true`, return `true`. Otherwise, return `false` after checking all possibilities.

Word Search (Backtracking)

Progress1 / 1

Ready to start.

Word Search (Backtracking/DFS)


class Solution:
    def exist(self, 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
            
            # Mark the cell as visited
            temp = board[r][c]
            board[r][c] = '#'
            
            # Check neighbors
            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))
            
            # Backtrack
            board[r][c] = temp
            return found

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