Word Search

Problem Description

Given an m × 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.

Examples

Constraints

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

Exploring the Grid with Backtracking DFS

To find the word, we must search for the first character in the grid. Once found, we perform a Depth-First Search (DFS) in all four cardinal directions to locate the second character, and so on.

The main challenge is preventing the path from visiting the same cell twice. We can track visited cells using a hash set, which uses extra space. Alternatively, we can mark cells as visited in-place by temporarily overwriting the cell character with a placeholder (like #) before recursing. After returning from the child calls, we restore the original character. This is backtracking.

Solution 1: Backtracking DFS (In-Place)

Perform a DFS search from each cell in the grid, marking cells visited in-place during the traversal.

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) return true; // matched all characters

        // boundary and character mismatch checks
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(i)) {
            return false;
        }

        char temp = board[r][c];
        board[r][c] = '#'; // mark as visited

        // search in all 4 directions
        boolean found = dfs(board, word, r + 1, c, i + 1) ||
                        dfs(board, word, r - 1, c, i + 1) ||
                        dfs(board, word, r, c + 1, i + 1) ||
                        dfs(board, word, r, c - 1, i + 1);

        board[r][c] = temp; // backtrack (restore original character)
        return found;
    }
}

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  # matched all characters

            # boundary and character mismatch checks
            if (
                r < 0
                or r >= rows
                or c < 0
                or c >= cols
                or board[r][c] != word[i]
            ):
                return False

            temp = board[r][c]
            board[r][c] = "#"  # mark as visited

            # search in all 4 directions
            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] = temp  # backtrack (restore original character)
            return found

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

#include <vector>
#include <string>

class Solution {
private:
    bool dfs(std::vector<std::vector<char>>& board, const std::string& word, int r, int c, int i) {
        if (i == word.length()) return true; // matched all characters

        // boundary and character mismatch checks
        if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size() || board[r][c] != word[i]) {
            return false;
        }

        char temp = board[r][c];
        board[r][c] = '#'; // mark as visited

        // search in all 4 directions
        bool found = dfs(board, word, r + 1, c, i + 1) ||
                     dfs(board, word, r - 1, c, i + 1) ||
                     dfs(board, word, r, c + 1, i + 1) ||
                     dfs(board, word, r, c - 1, i + 1);

        board[r][c] = temp; // backtrack
        return found;
    }

public:
    bool exist(std::vector<std::vector<char>>& board, std::string word) {
        for (int r = 0; r < board.size(); r++) {
            for (int c = 0; c < board[0].size(); c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }
};

Complexity Analysis:

• Time Complexity: O(N * 3^L) where N is the total number of cells on the board (rows * cols), and L is the length of the word. At the first node, we have 4 directions, and subsequent steps have at most 3 choices (we cannot go back to the parent cell).
• Space Complexity: O(L) representing the recursion stack depth, which is bounded by the length of the word.

Where it breaks: If the word contains many duplicate characters and the grid has a matching dense cluster, backtracking will explore many dead branches before returning false, which can cause execution times to spike.

Common Mistakes

• Forgetting to restore the cell character. If you don’t execute board[r][c] = temp during backtracking, cells remain marked as #, preventing other valid paths from using them.
• Checking bounds after indexing array. You must verify that coordinates are in-bounds before evaluating board[r][c] != word.charAt(i) to avoid index out of bounds exceptions.
• Not short-circuiting the recursion. If a direction match evaluates to true, return immediately instead of evaluating the remaining directions to optimize speed.

Frequently Asked Questions

Why is this in-place marking safe? It is safe because we restore the original character immediately after the recursive calls return. The grid returns to its original state when the outer function completes.

What is the maximum recursion depth? The maximum depth is the word length L, which is constrained to 15. Stack overflow is not a concern.

What does this problem test in interviews? It tests your ability to write recursion on 2D matrices, manage visited state without extra allocations, and handle coordinates boundaries correctly.

← All Problems