Word Search

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 1:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” Output: true

Example 2:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE” Output: true

Example 3:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB” Output: false

Constraints:

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

Follow up: Could you use search pruning to make your solution faster with a larger board?

Approach: DFS with Backtracking (Optimal Solution)

Algorithm

1. Try every cell (i, j) as the starting point of the word
2. Define dfs(i, j, k): can the suffix of the word starting at index k be found starting from cell (i, j)
3. In dfs:
   • If the current board cell does not match word[k], return false
   • If k is the last index, the whole word matched, return true
   • Temporarily mark the current cell as visited (set it to '0')
   • Recurse into the four neighbors for index k + 1
   • Restore the original character (backtrack) and return the result
4. Return true if any starting cell succeeds

Key Insight

The board is modified in place during exploration and restored after, which prevents revisiting the same cell while still allowing later searches to reuse it. The '0' sentinel acts as the visited marker, so no separate visited matrix is needed.

Time & Space Complexity

• Time Complexity: O(m × n × 3^k) - each cell starts a search that branches into at most 3 directions (one is always the cell we came from)
• Space Complexity: O(k) - recursion depth equals the word length; also O(m × n) for the board mutation in the worst case

Java Implementation

public class WordSearch {

    private int m;
    private int n;
    private String word;
    private char[][] board;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        this.board = board;
        this.word = word;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int i, int j, int k) {
        if (board[i][j] != word.charAt(k)) {
            return false;
        }
        if (k == word.length() - 1) {
            return true;
        }
        char c = board[i][j];
        board[i][j] = '0'; // mark as visited
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int u = 0; u < 4; u++) {
            int x = i + dirs[u];
            int y = j + dirs[u + 1];
            if (x >= 0 && x < m && y >= 0 && y < n
                && board[x][y] != '0'
                && dfs(x, y, k + 1)) {
                return true;
            }
        }
        board[i][j] = c; // backtrack
        return false;
    }
}

Example Walkthrough

For board and word = "ABCCED":

1. Start at (0,0) = ‘A’ matches word[0], mark visited
2. Recurse to (0,1) = ‘B’ matches word[1], then (0,2) = ‘C’ matches word[2]
3. (1,2) = ‘C’ matches word[3], then (2,2) = ‘E’ matches word[4]
4. (2,1) = ‘D’ matches word[5] = last character → return true

For word = "ABCB": the search reaches (1,1) = ‘F’ which cannot match 'B', and every other branch fails, so return false.

Follow-up: Search Pruning

For larger boards, prune early:

1. Character Frequency Check: If the board contains fewer occurrences of some letter than the word requires, return false immediately
2. Reverse Word Check: If the first character of the word is rarer than the last character, search the reversed word so fewer starting cells are tried
3. Early Termination: Stop the whole search as soon as any branch succeeds

Key Insights

1. In-place Marking: Temporarily setting cells to '0' avoids extra visited arrays
2. Backtracking: Restoring the cell after each failed branch allows other paths to reuse it
3. Direction Reduction: From any cell, at most 3 neighbors are useful (the one we came from is skipped)
4. Pruning Power: Frequency and reversal pruning dramatically cut search time on large boards

The DFS with backtracking is the optimal solution, providing O(m × n × 3^k) time and O(k) space.