Problem Overview

You are given an m x n grid of characters called board and a string word.

You need to determine whether the word exists in the grid.

Rules:

• The word must be constructed from sequentially adjacent cells

• Adjacent means up, down, left, or right

• The same cell cannot be used more than once in a single path

This problem is frequently asked by Google because it tests recursion, backtracking, and search pruning.

Example

Input:

board = [
  [A B C E],
  [S F C S],
  [A D E E]
]
word = "ABCCED"

Valid path:

A → B → C → C → E → D

Output:

true

Approach 1: Probability / Try-All Paths Idea

Conceptually:

• Start from every cell

• Try all possible paths

• Move in all directions

• Track whether the word is formed

Disadvantage:

• Number of paths grows very fast

• Massive repetition of the same states

• Not feasible without pruning

This idea is only theoretical.

Approach 2: Greedy Strategy

A greedy thought could be:

• Always move to the next matching character as soon as you see it

Why it fails:

• A correct character early may lead to a dead end later

• Greedy decisions cannot be undone

• Word search requires exploring and reverting decisions

Greedy does not work for this problem.

Approach 3: Recursion Without Backtracking

Recursive idea:

• Move forward if the next character matches

• Do not revisit cells

Disadvantages:

• Once a path fails, you cannot recover

• Blocks other valid paths

• Produces wrong answers

Backtracking is mandatory here.

Best Approach: DFS with Backtracking

Core Idea

• Try to build the word character by character

• Use DFS to explore neighbors

• Mark a cell as visited while exploring

• Restore it after finishing the path

This allows trying all possible paths safely.

DFS Logic

For each cell:

1. If current index equals word length, the word is found

2. If cell is out of bounds or character does not match, stop

3. Temporarily mark the cell as visited

4. Explore all four directions

5. Restore the cell value after exploration

This is classic backtracking.

Search Pruning Optimization (Follow-Up)

Google expects pruning for better performance.

Step 1: Character Frequency Check

• Count characters in the board

• If the board does not contain enough characters for the word, return false immediately

This avoids unnecessary DFS calls.

Step 2: Word Reversal Optimization

Observation:

• DFS starts from the first character of the word

• If the first character is very common, DFS will start many times

Optimization:

• Compare frequency of the first and last character

• If the first character is more frequent, reverse the word

• This reduces the number of DFS starting points

Time and Space Complexity

• Time: exponential in the worst case, but heavily reduced by pruning

• Space: limited by recursion depth, at most the word length

Final Code (DFS + Backtracking + Pruning)

class Solution {
public:
    int m, n;

    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int idx) {
        if (idx == word.size())
            return true;

        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[idx])
            return false;

        char temp = board[i][j];
        board[i][j] = '#';

        bool found =
            dfs(board, word, i + 1, j, idx + 1) ||
            dfs(board, word, i - 1, j, idx + 1) ||
            dfs(board, word, i, j + 1, idx + 1) ||
            dfs(board, word, i, j - 1, idx + 1);

        board[i][j] = temp;
        return found;
    }

    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();

        unordered_map<char, int> freq;
        for (auto& row : board)
            for (char c : row)
                freq[c]++;

        for (char c : word) {
            if (--freq[c] < 0)
                return false;
        }

        if (freq[word[0]] > freq[word.back()])
            reverse(word.begin(), word.end());

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }
};