Word Search II

1. Problem & Core Objective

Given an m × n board of characters and a list of words, return every word that can be formed by a path of adjacent cells (horizontally or vertically). A cell may not be reused within a single word.

board = o a a n          words = ["oath","pea","eat","rain"]
        e t a e
        i h k r          →  ["oath", "eat"]
        i f l z

Constraints: 1 <= m, n <= 12 · 1 <= words.length <= 3 × 10^4 · 1 <= word.length <= 10 · lowercase letters

What's actually being tested: recognising that running a board DFS once per word repeats almost all the work, and that a trie lets you run the board search once for all words simultaneously — pruning the instant no word can continue. It's the best demonstration in the 150 of a trie's negative answer being the valuable part.

Let k = number of words, L = maximum word length.

2. First-Principles Thought Process

Start from the single-word version

LeetCode 79 (Word Search I) asks whether one word exists on the board. The answer is a DFS from every cell, matching characters as you go, marking cells visited to prevent reuse.

The obvious extension: do that k times, once per word.

Why that's wasteful

With k = 3 × 10^4 words, you'd restart the whole board traversal 30,000 times. And most of that work is identical — every word beginning with o re-explores the same o cells, re-walks the same neighbours, and only diverges at the second character.

The reframe

Instead of asking "is this word on the board?" k times, ask once:

"walking from this cell, do any of my words still match?"

That question is exactly what a trie answers. Build a trie of all k words, then DFS the board once, stepping the trie in lockstep with the board path.

The pruning is the point

At each board cell, check whether the current trie node has a child for that letter:

• No child → no word in the entire dictionary continues this way. Abandon immediately, without exploring a single neighbour.
• Child exists → descend both the board and the trie. If the new node is marked isEnd, a word just completed — record it.

The k factor disappears: O(k · m · n · 4^L) becomes O(m · n · 4^L). All k words share one traversal.

Two refinements that matter

Collect each word once. A word may be reachable by several paths. Rather than deduplicating a list afterwards, clear the isEnd marker when you collect it — storing the word itself in the node makes this natural.

Prune consumed leaves. After collecting a word, if its node now has no children, it's dead. Removing it shrinks the trie as the search proceeds, so later cells prune even faster. On adversarial inputs this is the difference between passing and timing out.

3. Solution Paths

Approach 1 — Run Word Search I once per word (brute force)

public List<String> findWords(char[][] board, String[] words) {
    List<String> result = new ArrayList<>();
    for (String w : words)
        if (exists(board, w)) result.add(w);
    return result;
}

private boolean exists(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;
    if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || b[r][c] != word.charAt(i))
        return false;

    char saved = b[r][c];
    b[r][c] = '#';                                   // mark visited
    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;                                 // restore
    return found;
}

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

Counter-questions on this approach

⭐ "Each individual search is optimal. So where does it lose?"

In the repetition across words. The k searches are almost entirely the same work — every word starting with o re-explores the same o cells and the same neighbourhoods, diverging only at the second character.

With k = 3 × 10^4 and a 12×12 board, that's 30,000 full board traversals. The per-word DFS is fine; running it 30,000 times is not.

⭐ "How would you share the work?"

By inverting the loop. Instead of "for each word, search the board", do "walk the board once, and at each step ask which words are still alive". That question needs a structure that holds all k words indexed by prefix — which is a trie.

"What does b[r][c] = '#' accomplish?"

It marks the cell as in-use for the current path, so a word can't reuse a cell. Overwriting in place avoids a separate visited array, and restoring it on the way out is the backtracking step.

The '#' must be a character that can't appear in any word — lowercase letters only, so it's safe. Same sentinel discipline as everywhere else: confirm it's outside the data's range.

"Is the bound 4^L or 3^L?"

Practically 3^L after the first step, since you never immediately walk back into the cell you came from — it's marked. 4^L is the loose bound. With L = 10 that's 3^10 ≈ 59,000 per starting cell, times 144 cells, times 30,000 words — clearly too much.

Approach 2 — One DFS guided by a trie (optimal)

class Solution {
    private static class Node {
        Node[] children = new Node[26];
        String word;                       // the full word, non-null only at an end
    }

    public List<String> findWords(char[][] board, String[] words) {
        Node root = buildTrie(words);
        List<String> result = new ArrayList<>();

        for (int r = 0; r < board.length; r++)
            for (int c = 0; c < board[0].length; c++)
                dfs(board, r, c, root, result);

        return result;
    }

    private Node buildTrie(String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node node = root;
            for (char ch : w.toCharArray()) {
                int i = ch - 'a';
                if (node.children[i] == null) node.children[i] = new Node();
                node = node.children[i];
            }
            node.word = w;                 // store the word itself at its end node
        }
        return root;
    }

    private void dfs(char[][] board, int r, int c, Node node, List<String> out) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;

        char ch = board[r][c];
        if (ch == '#') return;                       // already on the current path
        Node next = node.children[ch - 'a'];
        if (next == null) return;                    // PRUNE: no word continues here

        if (next.word != null) {                     // a word ends here
            out.add(next.word);
            next.word = null;                        // collect it only once
        }

        board[r][c] = '#';
        dfs(board, r + 1, c, next, out);
        dfs(board, r - 1, c, next, out);
        dfs(board, r, c + 1, next, out);
        dfs(board, r, c - 1, next, out);
        board[r][c] = ch;                            // restore
    }
}

Trace — the example board, starting at (0,0) = o:

And starting at (3,3) = z: root.children['z'-'a'] is null, so it returns before exploring any neighbour — one array lookup rejects that entire starting cell.

• Time O(m · n · 4^L) · Space O(total characters) for the trie

Counter-questions on this approach

⭐ "Why store the whole word in the node instead of a boolean isEnd?"

So I can collect it without reconstructing it. With a boolean I'd have to carry a StringBuilder down the recursion and append/remove at each level — correct, but more state to get wrong on backtracking.

Storing the word costs one reference at the end nodes only, and it makes out.add(next.word) a single line. It also makes the deduplication trick natural: setting next.word = null both marks it collected and removes the flag.

⭐ "Why null the word after collecting instead of deduplicating at the end?"

Because a word can be reachable by many distinct paths, and each would add a duplicate. Deduplicating afterwards works but wastes the work of finding it repeatedly.

Nulling it means the second path reaching that node simply doesn't record anything — and I keep a List rather than needing a Set. It's the cheaper fix and it happens at exactly the right moment.

⭐ "Where is the pruning, precisely?"

The line if (next == null) return;. That's one array index, and it means no word in the entire dictionary has this prefix — so the search abandons immediately without touching a single neighbour.

That's the trie's negative answer, and it's why the k factor disappears. The naive version discovers a dead end only after matching the whole word against one candidate; here a dead end is known after one character, for all k words at once.

"Why check ch == '#' before the trie lookup?"

Because '#' - 'a' is negative and would throw ArrayIndexOutOfBoundsException. The visited marker has to be excluded before it's used as an index. It's a real ordering dependency, not defensive noise.

"You mutate the caller's board. Is that acceptable?"

It's restored on the way out, so the board is unchanged when findWords returns. But it's temporarily corrupted during the call, which makes it unsafe for concurrent readers — same caveat as the interleaving trick in Copy List With Random Pointer. A separate boolean[][] visited avoids it at the cost of O(m·n) space.

"What's the actual complexity? The k really vanishes?"

From the time bound, yes — the board traversal no longer depends on k. Building the trie is O(k · L), which is paid once, and the trie occupies O(k · L) space in the worst case.

So it's O(k · L) to build plus O(m · n · 4^L) to search, versus O(k · m · n · 4^L). With k = 3 × 10^4, m = n = 12, L = 10, that's the difference between passing and timing out.

"Could you prune the trie further?"

Yes, and it's the standard refinement. After collecting a word, if the node has no children it's dead — remove it from its parent. That shrinks the trie as the search runs, so later starting cells prune sooner. It needs a parent reference or a recursive dfs returning whether the child became empty. On adversarial inputs (many words sharing long prefixes) it's a significant win.

Comparison

4. Why the Optimal Wins

The naive version's cost is k times a board traversal because it asks a per-word question. The trie version asks a per-prefix question, and all k words share every prefix they have in common — which, for a real dictionary, is most of the early work.

The decisive mechanism is the negative answer. The naive DFS learns "this path is dead for word w" only after failing to match w; it then repeats the same walk for w'. The trie says "this path is dead for every word" after a single array lookup.

That's the general lesson: a trie is worth building not because lookup is faster — a hash set ties on that — but because it can refute an entire set of candidates at once.

The framing worth keeping:

When you'd otherwise run the same search once per candidate, put the candidates in a trie and run the search once. Failure then prunes all candidates simultaneously.

5. Java Prerequisites

Trie node carrying the word

private static class Node {
    Node[] children = new Node[26];
    String word;                 // non-null only where a word ends
}

Grid DFS with in-place visited marking

char ch = board[r][c];
board[r][c] = '#';               // mark
... recurse into 4 neighbours ...
board[r][c] = ch;                // restore — this is the backtrack

The sentinel must be outside the alphabet, and must be checked before being used as an index.

Bounds check first

if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;

Ordering matters — board[r][c] after an out-of-range r throws.

Collect-once by nulling

if (next.word != null) { out.add(next.word); next.word = null; }

Marks it collected and prevents duplicates in one assignment.

6. Interview Communication Guide

Clarifying questions: Can a cell be reused across different words (yes — only within one word is it forbidden)? Can the same word appear twice in the input (assume not; nulling handles it anyway)? Does the output order matter (no)? How large is words (3 × 10^4 — this is what rules out the per-word approach)?

The pitch

"The single-word version is a DFS from every cell, marking cells to prevent reuse within a path. The obvious extension is to run it once per word — but with 30,000 words that's 30,000 full board traversals, and almost all of that work is duplicated. Every word starting with o re-explores the same cells and only diverges at the second character.

So I invert the loop. Instead of 'for each word, search the board', I walk the board once and ask at each step: do any of my words still match this path?

That question is what a trie answers. I build a trie of all the words, then DFS the board stepping the trie in lockstep. At each cell I look up the current trie node's child for that letter.

If there's no child, no word in the whole dictionary continues this way, so I return immediately without exploring a single neighbour. That one array lookup prunes all 30,000 words at once — and it's the reason the k factor disappears from the traversal.

If the child exists, I descend both, and if that node marks the end of a word I collect it.

Two details. I store the word itself at its end node rather than a boolean, so collecting it doesn't require carrying a StringBuilder down the recursion. And I null it after collecting, because a word may be reachable by several paths — that deduplicates at the moment of discovery instead of afterwards.

O(k · L) to build the trie, then O(m · n · 4^L) to search, versus O(k · m · n · 4^L).

A further refinement worth mentioning: after collecting a word, if its node has no children it's dead and can be removed from its parent. That shrinks the trie as the search runs, so later cells prune faster — which matters on inputs with many words sharing long prefixes."

Edge cases to volunteer:

Name the prefix pair and the two-path case. The first checks you collect a word and keep descending rather than returning; the second is what the nulling exists for, and a list-plus-dedupe solution silently does more work to reach the same answer.

7. Follow-Up Questions — Modified Constraints

⭐ "Implement the leaf-pruning refinement properly."

Make dfs return whether the child node became empty, and have the parent null that slot. Or give each node a child count, decremented when a child dies. The effect is that the trie shrinks as words are found, so a dictionary with many long shared prefixes degrades gracefully instead of re-walking dead branches.

⭐ "What if the board were 1000 × 1000?"

m · n grows to 10^6 starting cells, so the constant matters far more. The trie's first-character pruning does most of the work — precompute the set of letters that begin any word and skip start cells not in it. You could also bucket start cells by letter and only launch DFS from cells whose letter has a root child, which is the same idea made explicit.

"What if words could be up to 100 characters?"

4^L becomes astronomical, but the trie saves you: a path can only continue while some word matches, so the effective depth is bounded by the longest word that actually matches, not by L. That's a case where the real cost is far below the bound — worth stating, because the formula looks alarming.

"Allow diagonal adjacency."

Eight neighbours instead of four, so the branching becomes 8^L. Structurally identical — just more recursive calls. The trie pruning becomes more valuable, since it cuts a wider tree.

"Return the path for each word, not just the word."

Carry the cell coordinates down and snapshot them when a word completes. O(L) extra per found word. The nulling trick still works, but now you'd want the first path found, so nulling on first collection gives exactly that.

"What if words were added or removed between queries on the same board?"

Keep the trie as persistent state and mutate it, then re-run the board search. Better, if the board is fixed and the dictionary changes often: precompute every string the board can produce up to length L into a set — expensive once, O(1) per query after. That's the right trade when queries greatly outnumber board changes.

"Could you use a hash set of words instead of a trie?"

Only with a different algorithm: enumerate every board path up to length L and test membership. That's O(m · n · 4^L) paths, each costing O(L) to hash — so no pruning at all, since a hash set can't tell you a prefix is dead. It's the clearest demonstration of why the prefix query, not the lookup speed, is what makes a trie the right structure here.