Course4all
Join us on telegram
Home/dsa/Backtracking/Word Search

Word Search

Master this topic with zero to advance depth.

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.

← Previous QuestionLetter Combinations of a Phone Number
Next Question →N-Queens