212. Word Search II

The naive read of Word Search II is “run Word Search once per word,” and that’s exactly the trap. With tens of thousands of words that blows up. The fix is a Trie: fold every word into one shared prefix tree, then walk the board a single time and let the tree tell you which paths are still worth chasing.

The problem

You get a grid of letters and a list of words. Return every word from the list that can be spelled by walking the grid through horizontally or vertically adjacent cells, never reusing a cell within one word. (Full statement on LeetCode.)

Say the board holds c a t across the top row and dog down the first column, and your list is ["cat", "car", "cot"]. Only cat traces a real path, so that’s all you return.

Intuition: let the Trie prune dead paths

Searching each word on its own repeats work. cat, car, and cot all start by finding a c, then two of them look for an a right after — the same cell scans get redone once per word.

A Trie collapses that. Insert every word and shared prefixes merge into shared branches. Now the DFS carries a Trie node alongside the board position, and the two move in lockstep: step to a neighboring cell only if the current node has a child for that letter. The moment a partial path has no matching child, the whole subtree of words under it is impossible, and you stop — one check kills many candidates at once.

That pruning is the entire win. Naively it’s $O(W \cdot m \cdot n \cdot 4^L)$ for $W$ words; the Trie makes it $O(m \cdot n \cdot 4^L)$ where $L$ is the longest word, because the board is walked once and the tree gates every branch.

Solution

Store the finished word on its terminal node instead of a boolean flag — then when DFS lands on it, the answer is right there, and setting it back to null dedupes for free.

class Solution {

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) insert(root, w);

        List<String> found = new ArrayList<>();   // fresh per call — no leaked state
        for (int r = 0; r < board.length; r++)
            for (int c = 0; c < board[0].length; c++)
                dfs(board, r, c, root, found);

        return found;
    }

    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> found) {
        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

        TrieNode next = node.kids[ch - 'a'];
        if (next == null) return;            // no word runs through here — prune
        if (next.word != null) {
            found.add(next.word);
            next.word = null;                // take it once, avoid duplicates
        }

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

    private void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.kids[i] == null) node.kids[i] = new TrieNode();
            node = node.kids[i];
        }
        node.word = word;
    }

    private static class TrieNode {
        TrieNode[] kids = new TrieNode[26];
        String word = null;                  // non-null only on a word's last node
    }
}

Complexity

Let $m \times n$ be the board, $L$ the longest word, and $N$ the number of words.

	Time	Space
Trie + DFS	$O(S + m \cdot n \cdot 4^L)$	$O(N \cdot L)$

The $S$ is the total length of all words, paid once to build the Trie ($S = \sum |\text{word}|$, up to $N \cdot L$). The $4^L$ is the worst-case branching of the DFS (up to four directions, depth $L$), and the Trie holds up to $N \cdot L$ nodes.

In an interview

Open by naming the anti-pattern out loud: “I won’t run Word Search per word — I’ll build a Trie so one board traversal covers all of them.” That framing alone signals you’ve seen the pattern. Then walk the # marker as your visited state and stress that you restore it on the way out, since a forgotten restore is the classic bug that quietly blocks valid paths.

The trap they’ll probe is duplicates: if a word appears through two different paths, do you emit it twice? Setting next.word = null after the first hit answers that cleanly. If you have time, mention pruning leaf Trie nodes as you consume words — it keeps the tree shrinking on huge inputs.

This sits at the top of the Trie pattern family. It’s really Implement Trie supplying the data structure and Add and Search Word supplying the DFS-through-a-Trie idea — Word Search II just runs both on a 2D board.

References

• LeetCode 212 — Word Search II