MANG Problem #3: Word Search II (Hard)

1. Problem Statement

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. Approach: Trie-Optimized Backtracking

The naive approach is to run a separate DFS for every word in the dictionary.

Complexity: $O(words \times MN \times 3^L)$ where $L$ is word length. This is way too slow.

The "Aha!" Moment: Simultaneous Search

Instead of searching for each word, search for all words at once. We build a Trie of the dictionary. As we traverse the grid with DFS, we move through the Trie simultaneously. If the path on the grid doesn't exist in the Trie, we prune the search immediately.

3. Java Implementation

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word; // Store 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];
    if (ch == '#' || node.children[ch - 'a'] == null) return;
    
    node = node.children[ch - 'a'];
    if (node.word != null) {
        res.add(node.word);
        node.word = null; // Mark as found to avoid duplicates
    }

    board[r][c] = '#'; // Mark as visited
    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()) {
            if (curr.children[c - 'a'] == null) curr.children[c - 'a'] = new TrieNode();
            curr = curr.children[c - 'a'];
        }
        curr.word = w;
    }
    return root;
}

4. 5-Minute "Video-Style" Walkthrough

The Pruning: Imagine the grid has 'o' $\rightarrow$ 'a' $\rightarrow$ 't' $\rightarrow$ 'z'. If our Trie only contains "oath", as soon as the DFS hits 'z', it checks the Trie, sees no child for 'z', and instantly returns. This saves billions of unnecessary recursive calls.
The State: Instead of building strings like curr + ch, we just pass the TrieNode. This reduces string allocation overhead to zero.
Deduplication: By setting node.word = null after finding it, we handle the case where a word can be formed multiple ways on the board without using a HashSet.

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "The upper bound is $O(M \times N \times 4 \times 3^{L-1})$, where $L$ is the length of the longest word. However, the Trie pruning makes the average case significantly faster."
Interviewer: "How can we optimize space?"
You: "We can use a HashMap in the TrieNode instead of an array if the alphabet is large, or use a BitSet to track visited cells if we aren't allowed to modify the board."