Course4all

Word Search

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Backtracking.

Word Search

Backtracking on 2D Grids

This problem is a classic example of DFS on a grid. We need to find a sequence of adjacent cells that match the characters of a given word.

Core Rules

  1. Use each cell at most once per word (requires tracking visited cells).
  2. Move in four directions: Up, Down, Left, Right.

Performance Optimization

To avoid using O(M×N)O(M \times N) extra space for a visited array, we can temporarily modify the board with a special character (like '#') to mark a cell as visited, then restore it after recursion (Backtracking).
Find a word in a 2D grid using DFS. Includes visual traversal trace.
Medium

Examples

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

Level I: DFS Backtracking (Visited Set)

Intuition

Try starting at every cell (i,j)(i, j). If it matches word[0], explore its neighbors recursively.
Use a visited set to keep track of used cells in the current path. If we match all characters of the word, return true.
⏱ O(N * M * 3^L) where L is the length of the word.💾 O(L) for recursion stack.

Detailed Dry Run

Dry Run: board=[['A','B'],['C','D']], word="ABD" | Step | Cell | Char | Path | Action | | :--- | :---: | :--- | :--- | :--------------- | | 1 | (0,0) | 'A' | "A" | Match, try neighbors | | 2 | (0,1) | 'B' | "AB" | Match, try neighbors | | 3 | (1,1) | 'D' | "ABD"| Match! SUCCESS | | 4 | (1,0) | 'C' | - | No Match (from A) |
java
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(0, i, j, board, word, visited)) return true;
            }
        }
        return false;
    }
    private boolean dfs(int idx, int r, int c, char[][] board, String word, boolean[][] visited) {
        if (idx == word.length()) return true;
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || visited[r][c] || board[r][c] != word.charAt(idx)) return false;
        
        visited[r][c] = true;
        boolean found = dfs(idx + 1, r + 1, c, board, word, visited) ||
                        dfs(idx + 1, r - 1, c, board, word, visited) ||
                        dfs(idx + 1, r, c + 1, board, word, visited) ||
                        dfs(idx + 1, r, c - 1, board, word, visited);
        visited[r][c] = false; // backtrack
        return found;
    }
}
Approach 2

Level II: Optimized Backtracking (Frequency Pruning)

Intuition

Before starting DFS, check if the board contains enough characters to form the word.
Count the frequency of each char in the board and the word. If the board has fewer characters than the word for any char, return false immediately. This avoids O(N×M×3L)O(N \times M \times 3^L) work in impossible cases.
⏱ O(N * M + 3^L)💾 O(1) extra.

Detailed Dry Run

word="AAAAA", board has only two 'A's -> Return FALSE immediately.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionLetter Combinations of a Phone Number
Next Question →N-Queens