Word Search: DFS on a grid with visited marking

• Word Search finds whether a word can be traced in a grid by moving up, down, left, or right, using each cell at most once.
• DFS with backtracking tries each direction, marking the current cell to prevent reuse and restoring it on backtrack.
• Success condition is when the character index reaches the word length, meaning every character has been matched.
• Short-circuit OR across four directions returns true as soon as any path succeeds.
• Worst-case time is O(R * C * 4^L); space is O(L) for the recursion stack.

What is the Word Search problem?

Given a 2D board of characters and a target word, return true if the word can be formed by tracing a path through horizontally or vertically adjacent cells, where each cell is used at most once in the path. This is a classic grid backtracking problem.

package com.bank.service;

public class SecurityPhraseVerifier {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == word.charAt(0)
                        && dfs(board, r, c, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int r, int c,
                         String word, int index) {
        if (index == word.length()) return true;
        if (r < 0 || r >= board.length
                || c < 0 || c >= board[0].length
                || board[r][c] != word.charAt(index)) {
            return false;
        }
        char temp = board[r][c];
        board[r][c] = '#';  // mark visited
        boolean found = dfs(board, r-1, c, word, index+1)
                     || dfs(board, r+1, c, word, index+1)
                     || dfs(board, r, c-1, word, index+1)
                     || dfs(board, r, c+1, word, index+1);
        board[r][c] = temp;  // restore on backtrack
        return found;
    }
}

Why is backtracking necessary?

Each cell can be used at most once per path. Without marking the cell as visited, the DFS could loop back and use the same cell multiple times, giving incorrect results. Restoring the cell on backtrack allows other search paths starting from different cells to reuse it.

// Mark: prevent reuse within current path
char temp = board[r][c];
board[r][c] = '#';

// Try all four directions
boolean found = dfs(...);

// Restore: allow reuse in other paths
board[r][c] = temp;

How does the temporary overwrite trick work?

Instead of maintaining a separate boolean visited array, you temporarily replace the current cell's character with a sentinel (like '#') that can never match any letter in the word. After exploring all directions from this cell, you restore the original character. This saves O(R * C) space for the visited array.

// Before recursion: board[r][c] = '#'
// During recursion: any path that tries to revisit this cell sees '#'
//   which != word.charAt(index), so the guard rejects it
// After recursion: board[r][c] = original character

What is the time complexity?

In the worst case, every cell could be a starting point, and from each cell the DFS branches 4 ways at each step for up to L steps (the word length). This gives O(R * C * 4^L). In practice, mismatches prune most branches early, so the actual runtime is much better.

Worst case: every cell matches every letter of the word
  R * C starting cells
  × 4 directions per step
  × L steps deep
  = O(R * C * 4^L)

Practice: mismatches prune aggressively
  Most searches terminate after 1-2 steps

How does short-circuit evaluation help?

The OR operator evaluates left to right and returns true as soon as any direction succeeds, skipping the remaining directions. This means the first successful path stops the search immediately without exploring unnecessary alternatives.

boolean found = dfs(board, r-1, c, word, index+1)   // up
             || dfs(board, r+1, c, word, index+1)    // down
             || dfs(board, r, c-1, word, index+1)    // left
             || dfs(board, r, c+1, word, index+1);   // right
// If 'up' returns true, down/left/right are never called

What about the letter-frequency optimization?

Before starting the search, count the frequency of each letter on the board and in the word. If the board lacks enough of any letter, return false immediately without searching.

public boolean existOptimized(char[][] board, String word) {
    // Pre-check: does the board have enough of each letter?
    int[] boardFreq = new int[128];
    for (char[] row : board)
        for (char c : row) boardFreq[c]++;
    for (char c : word.toCharArray()) {
        if (--boardFreq[c] < 0) return false;
    }
    // Optional: if the last char is rarer, search reversed word
    return existInternal(board, word);
}

What are edge cases?

• Word longer than total cells: impossible, return false.
• Single-cell board matching single-character word: return true.
• Word requires the same character more times than it appears on the board: the frequency check catches this.
• Board has only one row or one column: the DFS naturally handles linear boards.

// Edge case: word longer than board
if (word.length() > rows * cols) return false;

// Edge case: single cell
// board = [['a']], word = "a" → true
// board = [['a']], word = "ab" → false

What are common mistakes?

The first mistake is forgetting to restore the cell after backtracking, which permanently marks cells as visited and blocks other search paths. The second mistake is checking for success after the direction checks instead of at the start of the function, which misses the base case. The third mistake is using a separate visited array but forgetting to unmark on backtrack.

// WRONG: forgets to restore
board[r][c] = '#';
boolean found = dfs(...);
// Missing: board[r][c] = temp;
// All future paths from other start cells can't use this cell!

// CORRECT:
board[r][c] = '#';
boolean found = dfs(...);
board[r][c] = temp;  // always restore

What should a senior engineer know?

The worst case of O(R * C * 4^L) makes this problem exponential in the word length. For very long words on large boards, additional pruning is essential. The reverse-word trick (search the word in reverse if the last character is rarer) can dramatically improve performance. In production at the National Bank of India, Rajesh used this pattern to verify that security codes embedded in a grid of stamped characters could be traced through adjacent cells, with the frequency pre-check failing fast on invalid grids.