Word Search

Backtracking on a Grid

Under the hood, the Word Search problem is a test of whether you can explore a 2D space carefully, manage visited state, and backtrack without corrupting future paths. Interviewers use it to see whether you respect boundaries and clean up state correctly under pressure.

Problem Statement

Given an m × 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 means horizontally or vertically neighboring (not diagonal).

• The same cell may not be used more than once in a single path.

Examples:

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

exist(board, "ABCCED") → true
exist(board, "SEE")    → true
exist(board, "ABCB")   → false

1. Clarify Requirements Before Jumping Into Code

Before writing anything, restate the rules.

Input: A 2D character grid and a target word string.

Output: Boolean - does the word exist as a connected path in the grid?

Key rules:

• Movement is up, down, left, right only - no diagonals.

• A cell cannot be reused within the same path.

• The word must be formed from adjacent cells - this is path-finding, not substring search.

Edge cases to raise:

• What if the word is longer than the total number of cells? Impossible by definition - return false immediately.

• What about repeated characters in the grid? The path can pass through multiple cells with the same character, as long as it doesn't revisit a cell.

• Does the board need to be preserved? Typically yes - even if we modify it temporarily during search, we must restore it.

2. Identify the Category of the Problem

We've already seen backtracking on abstract choice trees (Subsets, Permutations) and structured constraint grids (N-Queens, Sudoku). Word Search adds a new wrinkle: the search space is a 2D grid where moves are constrained by position, and the "choices" at each step are the four neighboring cells. The backtracking skeleton is identical - choose, explore, un-choose - but the state to manage is spatial rather than index-based.

DFS as an option comes to mind. We could consider starting from multiple points, with visited-state management and early termination.

3. Start With Brute Force to Build Intuition

The naive approach is to generate every possible path through the grid, convert each path to a string, and check for a match.

This solution is explosive. From any cell, you can move in up to 4 directions. At each subsequent cell, up to 3 more (you can't immediately reverse). A path of length L branches up to 4 × 3^(L-1) ways from a single starting cell, and there are m × n possible starting cells. For a 4×4 grid and a 6-character word, that's thousands of paths just from one starting cell.

More importantly, most paths fail immediately - the first cell doesn't even match the first character. We're wasting enormous effort generating paths we could have rejected instantly.

The fix: match characters as we go, not after the fact. The moment a cell doesn't match the next character we need, stop and backtrack. Don't generate the full path first.

4. Brainstorm More Solutions

Step 1: Flip the Approach

The brute force failed because it separated two things that should happen together: path generation and character matching. It built complete paths first, then checked them - which meant doing enormous work before learning whether a path was even worth exploring.

The natural fix is to ask: what if we checked validity while building the path? We already know we need to visit cells in sequence and match characters - that's just DFS. So at each cell, before exploring further, we simply ask: "does this cell match the character I need right now?"

If not, we stop immediately and try somewhere else.

Step 2: Define the Recursive State

What does each DFS call need to know?

• (r, c): The current cell we're standing on.

• index: How many characters we've matched so far; or equivalently, which character of the word we're trying to match next.

Base cases:

• If index == word.length(): we've matched every character. Return true.

• If (r, c) is out of bounds: invalid move. Return false.

• If board[r][c] != word.charAt(index): mismatch. Return false.

Otherwise: mark this cell as visited, explore all four neighbors with index + 1, then unmark the cell.

Step 3: Managing Visited State

This is the most important implementation detail. We can't revisit a cell within the same path - "ABCB" should return false even if the board has adjacent A, B, C cells, because reaching B the second time would require reusing it.

One option is to maintain a separate boolean[][] visited array. Mark before recursing, unmark after.

But is there a cleaner option? Do we need a whole new visited array, or could we temporarily modify the board itself? We could replace board[r][c] with a sentinel character like '#' before recursing. After the recursive call returns - whether it succeeded or failed - we restore the original character.

This works because:

• '#' won't match any letter in word, so any attempt to revisit the cell will fail the character check immediately.

• Restoring the character after each call means the modification is invisible to other paths - the board is always in its original state when we start exploring a new branch.

Let's trace "ABCB" on the example board to see why this correctly returns false:

Start at (0,0)='A', index=0: match. Mark '#'. Try neighbors.
  Move to (0,1)='B', index=1: match. Mark '#'. Try neighbors.
    Move to (0,2)='C', index=2: match. Mark '#'. Try neighbors.
      Move to (0,1)='#', index=3: mismatch → false
      Move to (0,3)='E', index=3: mismatch → false
      Move to (1,2)='C', index=3: mismatch → false
      Move to (-1,2): out of bounds → false
    Unmark (0,2) → 'C'
  Move to (1,1)='F', index=2: mismatch → false
  Move to (0,0)='#', index=2: mismatch → false (already visited)
  Unmark (0,1) → 'B'
... all paths exhausted → false

The '#' sentinel at (0,1) correctly blocked the path from trying to reuse B. When we unmark after the recursive call, the board is clean for any subsequent starting point.

Step 4: Structure the Outer Loop

DFS alone isn't enough - we need to try every cell as a potential starting point, so we'll need to add an outer loop to scan every cell. If the cell matches word[0], we launch DFS from it. If it doesn't match, we can immediately return false, since there's no need to explore further.

We could skip the word[0] check and let DFS handle it via the mismatch base case. But checking first avoids the overhead of a function call for every non-matching starting cell. On a large board with few matching first characters, this matters.

Step 5: One Useful Optimization - Frequency Check

Before searching at all, we could consider an optimization: count the frequency of each character in word and in board. If word requires more of any character than board contains, return false immediately. This has the same worst case time complexity but would save us time in practice. Mentioning this in an interview shows you know how to apply your skills to real-world problems, where small optimizations like this one can add up to huge cost savings at large scales.

Step 6: What about the iterative approach?

Those of you familiar with DFS might be wondering: should we consider the iterative implementation option for the DFS algorithm? The short answer is no - and it's worth being able to talk about why.

Iterative DFS using an explicit stack is a legitimate implementation technique, but for Word Search specifically, it would make the code significantly more complex without providing any meaningful benefit. Remember that the main reason to use the iterative approach is to avoid deep recursion stacks. Here, the recursion depth is bounded by the word length L, which is typically small (LeetCode constrains it to 15). Stack overflow isn't a real risk here.

More importantly, the in-place '#' marking technique that makes this solution clean depends directly on the call stack. With recursion, restoration is guaranteed: the board[r][c] = temp line always executes when a frame returns, whether the path succeeded or failed. With an explicit stack, you'd need to think carefully about how and when you unmark cells. The code becomes harder to write, harder to read, and harder to explain under interview pressure.

5. Trade-Offs at a Glance

Approach	Time	Space	Notes
Path generation + matching	O(m·n · 4^(m·n))	Large	Infeasible
DFS backtracking	O(m·n · 4 · 3^(L-1))	O(L)	Standard solution
DFS + frequency pre-check	O(m·n · 4 · 3^(L-1))	O(L)	Same worst case; faster in practice

The time complexity deserves careful derivation. For each of the m·n cells, we might launch a DFS that explores a path of length L (the word length). At the first step, we can move in 4 directions. At each subsequent step, we can move in at most 3 directions (we can't immediately backtrack to the cell we came from which is marked as visited). So the number of paths explored from a single starting cell is at most 4 · 3^(L-1). Multiply by m·n starting cells: O(m · n · 4 · 3^(L-1)), which simplifies to O(m · n · 3^L).

This is exponential in L, the word length - but L is typically small (bounded by m · n), and early mismatch pruning means the vast majority of paths are cut off long before reaching depth L. In practice the algorithm is fast; the exponential is a worst-case bound that rarely manifests on real inputs.

Space is O(L) for the recursion stack - at most L frames deep, one per matched character.

6. Pseudocode

for each cell (r, c) in board:
    if board[r][c] == word[0]:
        if dfs(r, c, 0):
            return true
return false

dfs(r, c, index):
    if index == word.length:
        return true                      ← matched everything

    if out of bounds:
        return false
    if board[r][c] != word[index]:
        return false                     ← mismatch, prune

    temp = board[r][c]
    board[r][c] = '#'                    ← mark visited

    found = dfs(r+1, c, index+1)
         || dfs(r-1, c, index+1)
         || dfs(r, c+1, index+1)
         || dfs(r, c-1, index+1)

    board[r][c] = temp                   ← restore (un-choose)
    return found

Note the short-circuit evaluation in the found assignment. Java's || operator stops as soon as one branch returns true - the remaining directions aren't explored. This is automatic early termination: the moment we find a valid path, we propagate true upward without doing unnecessary work.

7. Edge Cases

• Word longer than total cells: Can't exist - no path can be longer than m·n. Return false immediately.

• Single character word: DFS is called with index=0. If board[r][c] == word[0], we mark, then check index+1 == word.length() → return true. Works correctly.

• Repeated characters in the board: The '#' sentinel handles this. Multiple cells may have the same character, but within one path, a visited cell can't be reused.

• "AAA" on [["A","A"]]: The board has only two A's, but the word needs three. The DFS correctly returns false - at depth 2, both neighbors are either out of bounds or marked '#'.

8. Full Solution

public class WordSearch {

    public static boolean exist(char[][] board, String word) {
        int rows = board.length;
        int 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)) {
                    if (dfs(board, word, r, c, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private static boolean dfs(char[][] board, String word,
                                int r, int c, 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, word, r + 1, c, index + 1) ||
            dfs(board, word, r - 1, c, index + 1) ||
            dfs(board, word, r, c + 1, index + 1) ||
            dfs(board, word, r, c - 1, index + 1);

        board[r][c] = temp;             // restore
        return found;
    }
}

The two lines that matter most are board[r][c] = '#' and board[r][c] = temp. They're the entire visited-state mechanism. If you forget the restore, cells stay marked after backtracking, corrupting every subsequent search from that starting point. The bug would be subtle - some valid words would return false, and the failure would depend on the order cells are explored.

9. Test Your Solution

char[][] board1 = {
    {'A','B','C','E'},
    {'S','F','C','S'},
    {'A','D','E','E'}
};

System.out.println(exist(board1, "ABCCED")); // true
System.out.println(exist(board1, "SEE"));    // true
System.out.println(exist(board1, "ABCB"));   // false — can't reuse B

char[][] board2 = {{'A','A'}};
System.out.println(exist(board2, "AAA"));    // false — only two A's

char[][] board3 = {{'A'}};
System.out.println(exist(board3, "A"));      // true — single cell

10. Key Lessons for Future Problems

• Match incrementally, not after the fact. The core insight here is the flip from "generate paths, then check" to "check at every step, prune immediately on mismatch." This principle applies broadly: whenever you're searching for a path or sequence that must satisfy a condition, check the condition as early as possible rather than building the full candidate first.

• In-place marking is a clean visited-state technique. The '#' sentinel approach avoids allocating a separate visited array. The tradeoff is that it temporarily modifies input - which is fine as long as you restore it. This technique works whenever you can choose a sentinel that's guaranteed not to appear legitimately in the input. Always restore immediately after the recursive call, in the same stack frame that made the modification.

• Grid DFS is backtracking with spatial choices. The four-directional move array [(1,0), (-1,0), (0,1), (0,-1)] is the grid equivalent of the candidate loop in Combination Sum or the column loop in N-Queens. The structure is identical - loop over choices, check validity, recurse, undo. What changes is the domain of choices and the validity condition.

• Short-circuit evaluation is free pruning. Java's || operator stops evaluating as soon as it finds a true. Ordering your four directional calls so the most promising directions come first can meaningfully reduce work on average - though it doesn't change worst-case complexity.

• State leaks break backtracking silently. If you forget to restore board[r][c], the bug doesn't crash - it silently returns wrong answers for some inputs. This is one of the most common and hardest-to-debug mistakes in backtracking problems. The discipline of writing the restore line immediately after the recursive call - before you even think about what comes next - is a habit worth building.

  
  

Good Luck and Happy Coding!