MANG Problem #3: Word Search II (Hard)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

2. The Mental Model: The "Library Search"

Imagine you are looking for 1,000 different words in a massive grid of letters.

The Naive Way: Run a separate DFS for every single word in the dictionary.
- Complexity: $O(W \times M \times N \times 4^L)$ where $L$ is word length. This is catastrophically slow.
The Senior Way: Instead of searching for words, search the grid once and check if the characters you find form any of the words in the dictionary simultaneously.

To do this, you need a data structure that can tell you in $O(1)$ if a prefix you just found (e.g., "oa") could possibly lead to any word in your dictionary. This structure is a Trie (Prefix Tree).

3. Approach: Trie-Pruned Backtracking

We build a Trie from our dictionary. As we perform a DFS on the grid, we "walk" through the Trie at the same time.

Build Trie: Insert all words into the Trie.
DFS Starts: Start a DFS from every cell (r, c) in the grid.
Trie Pruning: At each step of the DFS:
- Check if the current character board[r][c] exists as a child of our current Trie node.
- If No: The current path is a dead end. PRUNE (return) immediately.
- If Yes: Move to the child Trie node and check if it's the end of a word.
Mark Visited: Temporarily change board[r][c] to a special character (like #) to prevent using the same cell twice in one word.

4. Visual Execution (Pruning Logic)

graph TD
    Start[Grid Cell 'O'] --> TrieRoot[Trie Root]
    TrieRoot -- child 'O' --> NodeO[Trie Node: O]
    NodeO -- child 'A' --> NodeA[Trie Node: OA]
    NodeA -- child 'T' --> NodeT[Trie Node: OAT]
    NodeT -- child 'Z' --> Prune[No 'Z' in Trie! STOP DFS]

5. Java Implementation

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word; // Optimization: Store the full word at the leaf
}

public List<String> findWords(char[][] board, String[] words) {
    List<String> res = new ArrayList<>();
    TrieNode root = buildTrie(words);
    
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs(board, i, j, root, res);
        }
    }
    return res;
}

private void dfs(char[][] board, int r, int c, TrieNode node, List<String> res) {
    char ch = board[r][c];
    // Base Cases: Out of bounds, Already visited, or Not in Trie
    if (ch == '#' || node.children[ch - 'a'] == null) return;
    
    node = node.children[ch - 'a'];
    if (node.word != null) {
        res.add(node.word);
        node.word = null; // Important: Deduplicate results!
    }

    board[r][c] = '#'; // Mark as visited
    
    // Explore 4 directions
    if (r > 0) dfs(board, r - 1, c, node, res);
    if (c > 0) dfs(board, r, c - 1, node, res);
    if (r < board.length - 1) dfs(board, r + 1, c, node, res);
    if (c < board[0].length - 1) dfs(board, r, c + 1, node, res);
    
    board[r][c] = ch; // Backtrack
}

private TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode curr = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
        }
        curr.word = w;
    }
    return root;
}

6. Verbal Interview Script (Staff Tier)

Interviewer: "Why is a Trie better than a HashSet for this problem?"

You: "While a HashSet can tell us if a full word exists, it cannot efficiently tell us if a specific prefix exists. In this problem, Pruning is the key to performance. With a Trie, as soon as I find a sequence of characters that doesn't form the start of any word in the dictionary, I can kill that recursive branch immediately. This saves us from billions of unnecessary DFS calls. Additionally, by storing the full word inside the Trie's leaf node, we eliminate the need to maintain a StringBuilder in our recursion, significantly reducing memory allocation overhead."

7. Performance Nuances (Staff Level)

Deduplication: Notice the line node.word = null. In some cases, a word like "oath" might be found via two different paths on the board. By clearing the word in the Trie after the first time we find it, we guarantee uniqueness without needing a Set<String> for our result list.
Board Modification: Modifying the board board[r][c] = '#' is a space-saving trick ($O(1)$ extra space). However, in a production multi-threaded environment, the input board would likely be immutable. In that case, we would use a boolean[][] visited array ($O(M \times N)$ space).

Key Takeaways

The Naive Way: Run a separate DFS for every single word in the dictionary.
Complexity: $O(W \times M \times N \times 4^L)$ where $L$ is word length. This is catastrophically slow.
The Senior Way: Instead of searching for words, search the grid once and check if the characters you find form any of the words in the dictionary simultaneously.