Word Search

1. Problem & Core Objective

Given an m × n grid of characters and a word, return true if the word exists in the grid. The word is formed from adjacent cells (horizontal or vertical), and the same cell may not be reused.

board = A B C E          word = "ABCCED"  →  true
        S F C S          word = "SEE"     →  true
        A D E E          word = "ABCB"    →  false   (B would be reused)

Constraints: 1 <= m, n <= 6 · 1 <= word.length <= 15 · letters only

What's actually being tested: backtracking on a grid rather than a list. The choices are the four neighbours, and the "un-choose" is restoring a cell you temporarily marked. It's the single-word version of Word Search II, which is where this technique pays off at scale.

2. First-Principles Thought Process

The same skeleton, different choices

Every previous question chose from an array. Here the choices at each step are the four neighbours of the current cell — but the shape is identical:

choose a neighbour → explore → un-choose

The new problem: preventing reuse

Subsets used i + 1 to move past an element. Permutations used a used[] array. On a grid there's no index ordering to exploit, so you need an explicit "currently on the path" marker.

Two options:

A separate boolean[][] visited — clean, and leaves the board untouched.

Overwrite the cell with a sentinel — board[r][c] = '#', restore on the way out. No extra allocation, but it temporarily corrupts the caller's data.

The sentinel must be a character that can't appear in the word. Letters only, so '#' is safe — but that's a fact to verify against the constraints, not assume.

Why the un-choose is mandatory here

board[r][c] = ch; on the way out is what lets a different path use that cell later. Without it, the first failed exploration permanently blocks cells, and subsequent starts silently fail.

This is the most visible instance of the un-choose in the section: forget it and the answer is wrong in a way that's hard to see, because early test cases often pass.

Where the search starts

The word could begin anywhere, so try every cell as a starting point: m × n launches, each a DFS.

The branching factor

Four neighbours at each step — but after the first, one of them is the cell you came from, which is marked. So it's effectively 3 onward choices, giving O(m · n · 3^L) where L is the word length.

At 6 × 6 with L = 15: 36 × 3^15 ≈ 5 × 10^8 worst case. The character check prunes almost all of it in practice, since most branches die on the first mismatched letter.

3. Solution Paths

Approach 1 — Enumerate all paths, then compare (brute force)

public boolean exist(char[][] board, String word) {
    for (int r = 0; r < board.length; r++)
        for (int c = 0; c < board[0].length; c++)
            if (buildAndCheck(board, r, c, new StringBuilder(),
                              new boolean[board.length][board[0].length], word))
                return true;
    return false;
}

private boolean buildAndCheck(char[][] b, int r, int c, StringBuilder path,
                              boolean[][] visited, String word) {
    if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || visited[r][c]) return false;
    if (path.length() >= word.length()) return false;              // depth cap

    visited[r][c] = true;
    path.append(b[r][c]);

    boolean found = path.toString().equals(word)                   // compare only at full length
                 || buildAndCheck(b, r+1, c, path, visited, word)
                 || buildAndCheck(b, r-1, c, path, visited, word)
                 || buildAndCheck(b, r, c+1, path, visited, word)
                 || buildAndCheck(b, r, c-1, path, visited, word);

    path.deleteCharAt(path.length() - 1);
    visited[r][c] = false;
    return found;
}

Build every path up to the word's length, then test whether it matches.

• Time O(m · n · 4^L · L) · Space O(L)

Counter-questions on this approach

⭐ "What's the key inefficiency?"

It checks the match only when the path reaches full length. So a path starting "X" when the word starts "A" is extended to 15 characters before being rejected.

The fix is to compare one character at a time: if board[r][c] != word.charAt(index), the branch is dead immediately. That prunes at depth 1 instead of depth L, and it's the difference between exploring the whole grid and exploring almost none of it.

⭐ "It also does path.toString().equals(word) at every node. How bad is that?"

toString copies the builder — O(L) — and equals is another O(L). Doing that at every node adds a factor of L to an already exponential search.

Matching character-by-character makes the test O(1) per node, because the path prefix is guaranteed correct by construction.

"Does it at least terminate?"

Yes, because of the depth cap and the visited array — a path can't exceed the word's length or revisit a cell. But the cap is compensating for a missing check, in the same way the depth cap in Combination Sum's brute force was.

Approach 2 — Character-by-character DFS with in-place marking (optimal)

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

private boolean dfs(char[][] b, int r, int c, String word, int i) {
    if (i == word.length()) return true;                       // consumed the whole word
    if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return false;
    if (b[r][c] != word.charAt(i)) return false;               // PRUNE at the first mismatch

    char saved = b[r][c];
    b[r][c] = '#';                                             // choose: mark as on-path

    boolean found = dfs(b, r+1, c, word, i+1) || dfs(b, r-1, c, word, i+1)
                 || dfs(b, r, c+1, word, i+1) || dfs(b, r, c-1, word, i+1);

    b[r][c] = saved;                                           // un-choose: restore
    return found;
}

Trace — finding "SEE" in the example board:

• Time O(m · n · 3^L) · Space O(L) recursion

Counter-questions on this approach

⭐ "Why check the character before marking rather than after?"

So that a mismatched cell is rejected without touching the board at all. If I marked first and then compared, I'd have to restore before every early return — three extra places to get it wrong.

Ordering the guards as bounds → character → mark means each early return happens before any mutation, so there's exactly one restore, paired with exactly one mark.

⭐ "What exactly goes wrong if you forget b[r][c] = saved?"

Cells stay marked after a failed exploration, so they're permanently unavailable. A later start that genuinely needs one of those cells silently fails, and the function returns false for a word that exists.

It's the worst kind of bug: early tests often pass, because the first start frequently succeeds or the blocked cells aren't needed. That's why the un-choose deserves to be stated as part of the template rather than remembered ad hoc.

⭐ "Why is '#' safe as the marker?"

Because the constraint says the board and word contain letters only, so '#' can never be a legitimate character and the comparison b[r][c] != word.charAt(i) correctly rejects a marked cell.

That's also why no separate visited check is needed — the marker is the visited check, folded into the character comparison. But it depends entirely on the sentinel being outside the alphabet, which I'd verify rather than assume. If the board could contain '#', I'd use a boolean[][].

"Why is the branching 3^L rather than 4^L?"

After the first step, one of the four neighbours is the cell you just came from — and it's marked, so the character check rejects it immediately. That leaves three viable directions.

4^L is the loose bound; 3^L is the honest one. At L = 15 that's 1.4 × 10^7 versus 10^9 — a meaningful difference in how alarming the number looks.

"How much does the character check actually prune?"

Enormously, in practice. Most starting cells fail at depth 0, and most branches fail at depth 1. The 3^L bound assumes every character matches everywhere, which requires a board of nearly identical letters — the adversarial input is something like a grid of all As with the word "AAAAAAAAAAAAAAB".

"Does it mutate the caller's board?"

Temporarily. Every marked cell is restored, so the board is identical when exist returns — but during the call it's corrupted, which makes it unsafe for a concurrent reader. A boolean[][] visited avoids that at O(m·n) space.

Comparison

4. Why the Optimal Wins

Both explore a search tree over grid paths. The difference is when a branch is abandoned.

The brute force builds a full-length path and then compares, so a path whose very first letter is wrong still costs O(L) work and 4^L exploration beneath it. Character-by-character matching kills that branch at depth 1.

That's the general principle behind all pruning: test the constraint at the earliest moment it can fail, not at the end.

The framing worth keeping:

On a grid, the choices are the four neighbours and the un-choose is restoring the cell. Mark in place with a sentinel outside the alphabet, and check the character before marking so every early return happens before any mutation.

5. Java Prerequisites

Grid DFS with in-place marking

if (i == word.length()) return true;                    // base case FIRST
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return false;   // bounds
if (b[r][c] != word.charAt(i)) return false;            // then the value check

char saved = b[r][c];
b[r][c] = '#';
... four recursive calls ...
b[r][c] = saved;

Guard order matters — bounds before indexing, and both before mutating.

Short-circuit || stops at the first successful direction, so a found word doesn't explore the remaining three.

String.charAt(i) is O(1). Avoid substring inside a recursion — it's O(L) per call and turns the search into O(L) times worse.

6. Interview Communication Guide

Clarifying questions: Can a cell be reused (no — within one word)? Are diagonals allowed (no, four directions)? May I modify the board (the in-place marker does, but restores it)? Can the board contain '#' (no — letters only, which is what makes the sentinel safe)?

The pitch

"Same backtracking skeleton as the array problems — the only difference is that the choices at each step are the four neighbours rather than elements of a list.

I try every cell as a starting point, since the word could begin anywhere, and from each I DFS matching one character at a time.

The important decision is matching character-by-character rather than building a path and comparing at the end. If the board character doesn't equal word.charAt(i), that branch is dead immediately — at depth 1 rather than depth L. Building the whole path first means a wrong first letter still costs a full-length exploration beneath it.

To stop a cell being reused within one word I mark it in place, overwriting with '#', and restore it on the way out. The sentinel works because the constraint says letters only, so '#' can never match a word character — which means the marker doubles as the visited check, folded into the same comparison. I'd verify that rather than assume it; if the board could contain '#' I'd use a separate boolean[][].

I order the guards as bounds, then character, then mark — so every early return happens before any mutation, and there's exactly one restore paired with exactly one mark.

The restore is the part that fails silently if forgotten: cells stay blocked after a failed exploration, so a later start that needs them returns false for a word that exists.

O(m · n · 3^L) — three rather than four because after the first step one neighbour is the cell you came from, already marked. O(L) stack."

Edge cases to volunteer:

Name "ABCB". It's the case that distinguishes "adjacent path" from "any sequence of matching letters" — a solution without the visited marker returns true and passes many other tests.

7. Follow-Up Questions — Modified Constraints

⭐ "Search for many words at once."

That's Word Search II. Running this once per word is O(k · m · n · 3^L); putting the words in a trie and walking the board once collapses the k factor, because a missing trie child prunes every word simultaneously. This question is the natural precursor.

⭐ "Allow a cell to be reused."

Then no marking is needed — but the search can loop forever, since you could bounce between two cells indefinitely. The word length bounds it: depth is capped at L, so it terminates at O(m · n · 4^L). Worth noting that removing a constraint made the bound worse, since three directions became four.

"Allow diagonal moves."

Eight neighbours, so O(m · n · 7^L). Structurally identical — a longer list of offsets. At L = 15 that's 4.7 × 10^12, so the character pruning becomes essential rather than merely helpful.

"Return the path, not just a boolean."

Carry a list of coordinates and snapshot it when i == word.length(). O(L) extra. The un-choose now removes from that list too — two mutations in, two out.

"What if the board were 1000 × 1000?"

A million starting cells. The first-character check prunes most of them in O(1), so precompute which cells hold word.charAt(0) and launch only from those. A useful refinement: if the word's last letter is rarer than its first, search for the reversed word instead — fewer starting points.

"Count how many distinct paths spell the word."

Drop the early return and keep a counter instead of returning on the first hit. Strictly slower, because the short-circuit disappears and every path must be explored to completion.