Word Search II Java Solution with Trie and DFS

Word Search II requires efficiently finding multiple words from a dictionary on a 2D board, making it an ideal candidate for Trie-based optimization to avoid redundant searches.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on the board dimensions and word list size?
2. Are duplicates in the word list allowed, and should we return them multiple times?
3. What format should the result be returned in - list, set, or array?
4. Can we modify the input board during the search process?
5. What's the expected time complexity for the follow-up - O(nm4^L) where L is max word length?

Restatement: Given a 2D character grid (board) and a list of words, find all words from the list that can be constructed by sequentially adjacent cells (horizontally or vertically) without reusing any cell within a single word construction.

Clarification:

• Input: A 2D char grid of size m×n and a list of words (strings)
• Output: All words from the list that exist as paths on the board
• Constraints: Board dimensions up to 12×12, word list up to 3×10^4 words, each word up to 10 characters
• Assumption: All board cells and words contain only lowercase English letters

Data Shape:

• Grid: 2D array of chars with dimensions m×n where 1 ≤ m,n ≤ 12
• Words: List of strings with length up to 10 characters each

Hidden Structure: The problem exhibits a classic backtracking pattern with prefix matching, where we can optimize by using a trie data structure to avoid redundant searches for words sharing common prefixes.

The core challenge is efficiently searching through multiple words simultaneously on a 2D grid while avoiding redundant computation and maintaining the constraint that each cell can only be used once per word path.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern for this problem is Trie-based backtracking. This combines:

• Trie data structure for efficient prefix lookup and word storage
• Backtracking algorithm for exploring all possible paths on the board
• DFS traversal with pruning to avoid unnecessary exploration

Wording that signals the pattern

The key phrases that signal this pattern:

• "Word Search" - suggests exploring paths on a grid with specific criteria
• "Multiple words" - indicates we need to handle several search targets simultaneously
• "Prefix matching" - implies we should leverage trie's prefix property for efficient searching

Why this problem fits that pattern

This problem requires finding multiple words on a 2D board where:

1. Each word is formed by sequentially adjacent cells (horizontally or vertically)
2. No cell can be reused in a single word
3. We're looking for words that exist in a dictionary

The trie data structure naturally handles the dictionary lookup efficiently, while backtracking with DFS allows us to explore all valid paths while pruning branches that can't lead to valid words.

Core insight needed to solve it

The key insight is that we can build a trie from all the target words and use it as a real-time prefix checker during our DFS traversal. This allows us to:

1. Stop exploring paths immediately when we know no valid word can be formed
2. Avoid re-searching the same prefix multiple times
3. Reduce redundant computation by leveraging the trie's structure

This approach transforms what could be an exponential search problem into a more manageable backtracking with intelligent pruning.

3. Approach Evolution

My first instinct is to use a brute force approach where I check every cell as a starting point and try to find each word by exploring all possible paths, but that would be O(n² × m × 4^L) where n is grid dimensions, m is word count, and L is average word length. That's too slow for large inputs.

Let me think about how to optimize this. I notice that we're looking for multiple words in a grid, and we're doing a lot of redundant work - we're exploring the same paths multiple times for different words. The key insight is that I can build a trie of all the target words and then traverse the grid once, using the trie to guide my search.

I notice that if I maintain a trie structure and traverse the grid in DFS fashion, I can avoid re-checking the same prefixes multiple times. When I'm at a cell and have a prefix that doesn't exist in any word, I can prune that search path entirely. This reduces the search space significantly.

The core insight is to use a trie (prefix tree) as a lookup structure for all words, and then perform a single DFS traversal of the grid while maintaining the current path as a string. At each step, I check if the current prefix exists in the trie - if not, I can stop exploring that path. If I reach a word end in the trie, I've found a valid word.

This approach reduces time complexity from exponential to O(m × n × 4^L) where we're still exploring at most 4 directions from each cell, but with early pruning.

The key invariants that must hold:

1. The current path string should always be a valid prefix in the trie (or we prune)
2. We must avoid visiting the same cell twice in a single path (using visited set)
3. When we find a complete word, we add it to results and mark it as found (to avoid duplicates)
4. We only continue DFS if the current prefix exists in our trie

The optimization comes from the fact that we're not exploring all possible paths - we're only exploring paths that could potentially form valid words, and we're doing this with a single pass through the grid.

4. Data Structure Choice

For this Word Search II problem, I'll use a Trie data structure as the primary container for the word dictionary, along with a 2D boolean matrix to track visited cells during DFS traversal.

Primary Data Structures

1. Trie (Prefix Tree) - Used to store all the words from the input dictionary

   • Why needed: Efficiently handles prefix-based searching and allows for early termination when a path doesn't match any word prefix
   • Time impact: O(M×L) to build where M is number of words and L is average word length
   • Space impact: O(M×L) worst case for storing all words

2. 2D Boolean Matrix - Used to track visited cells during DFS traversal

   • Why needed: Prevents reusing the same cell in a single word search path
   • Time impact: O(1) per cell access for visited status
   • Space impact: O(m×n) where m and n are board dimensions

Supporting Structures

3. HashSet - Used to store found words to avoid duplicates
   • Why needed: Ensures each word is added only once even if found through multiple paths
   • Time impact: O(1) average for add and contains operations
   • Space impact: O(K) where K is the number of found words

Why This Choice Is Optimal

The Trie structure provides the key optimization for this problem - it allows us to efficiently check if we're still on a valid prefix path while traversing the board. Without the Trie, we'd need to check each word individually at every position, leading to exponential time complexity.

The boolean matrix is essential for maintaining the constraint that we cannot reuse cells within a single word search path, which is fundamental to the problem's requirements.

class TrieNode {
    TrieNode[] children;
    String word;
    
    public TrieNode() {
        children = new TrieNode[26];
        word = null;
    }
}

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

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

Step 1: Build the Trie with all words: ["oath","pea","eat","rain"]

• Trie structure:
  • Root → 'o' → 'a' → 't' → 'h' (end of "oath")
  • Root → 'p' → 'e' → 'a' (end of "pea")
  • Root → 'e' → 'a' → 't' (end of "eat")
  • Root → 'r' → 'a' → 'i' → 'n' (end of "rain")

Step 2: Start DFS from each cell in the board

• Starting at (0,0) = 'o':
  • Path: "o" matches prefix in Trie
  • Continue DFS to adjacent cells

Step 3: At position (0,1) = 'a' with current path "oa"

• Path: "oa" matches prefix in Trie
• Continue DFS to adjacent cells

Step 4: At position (0,2) = 'a' with current path "oaa"

• Path: "oaa" does not match any prefix in Trie
• Backtrack and try other paths

Step 5: At position (0,1) = 'a' with current path "o"

• Path: "o" matches prefix in Trie
• Continue DFS to adjacent cells

Step 6: At position (1,0) = 'e' with current path "oe"

• Path: "oe" matches prefix in Trie
• Continue DFS to adjacent cells

Step 7: At position (1,1) = 't' with current path "oet"

• Path: "oet" matches prefix in Trie
• Continue DFS to adjacent cells

Step 8: At position (1,2) = 'a' with current path "oeta"

• Path: "oeta" matches prefix in Trie and reaches end of "oath"
• Add "oath" to results
• Mark this path as visited to avoid reuse

Step 9: Continue DFS from remaining cells

• When we reach "eat" path, it matches prefix and reaches end of "eat"
• Add "eat" to results

Step 10: When we exhaust all paths, return collected words: ["oath","eat"]

The key insight is that we're simultaneously traversing the board and the Trie, which allows us to efficiently prune paths that don't lead to valid words. Each DFS call maintains the current path and checks against the Trie for prefix validity, ensuring we don't explore unnecessary branches.

public List<String> findWords(char[][] board, String[] words) {
    List<String> result = new ArrayList<>();
    if (board == null || board.length == 0 || board[0].length == 0 || words == null || words.length == 0) {
        return result;
    }
    
    // Build the Trie with all words
    TrieNode root = buildTrie(words);
    
    // Start DFS from each cell in the board
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs(board, i, j, root, result);
        }
    }
    
    return result;
}

private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
    // Check bounds and visited status
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '#') {
        return;
    }
    
    char ch = board[i][j];
    // Check if current character exists in the Trie
    if (node.children[ch - 'a'] == null) {
        return;
    }
    
    // Move to the next node in the Trie
    node = node.children[ch - 'a'];
    
    // If we found a complete word, add it to results
    if (node.word != null) {
        result.add(node.word);
        node.word = null; // Avoid duplicate additions
    }
    
    // Mark current cell as visited
    char temp = board[i][j];
    board[i][j] = '#';
    
    // Explore all 4 adjacent cells
    dfs(board, i + 1, j, node, result);
    dfs(board, i - 1, j, node, result);
    dfs(board, i, j + 1, node, result);
    dfs(board, i, j - 1, node, result);
    
    // Restore the original character
    board[i][j] = temp;
}

6. Java Solution

import java.util.*;

public class WordSearchII {
    // Trie node definition
    static class TrieNode {
        TrieNode[] children;
        String word;
        
        public TrieNode() {
            children = new TrieNode[26];
            word = null;
        }
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        
        // Build trie from the given words
        TrieNode root = buildTrie(words);
        
        // Search for words starting from each cell
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, result);
            }
        }
        
        return result;
    }
    
    private void dfs(char[][] board, int row, int col, TrieNode node, List<String> result) {
        // Check bounds
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
            return;
        }
        
        char ch = board[row][col];
        
        // Skip visited cells or characters not in trie
        if (ch == '#' || node.children[ch - 'a'] == null) {
            return;
        }
        
        // Move to the next node in trie
        node = node.children[ch - 'a'];
        
        // If we found a complete word, add it to result
        if (node.word != null) {
            result.add(node.word);
            // Avoid adding the same word multiple times
            node.word = null;
        }
        
        // Mark current cell as visited
        board[row][col] = '#';
        
        // Explore all 4 directions
        dfs(board, row + 1, col, node, result);
        dfs(board, row - 1, col, node, result);
        dfs(board, row, col + 1, node, result);
        dfs(board, row, col - 1, node, result);
        
        // Restore the cell
        board[row][col] = ch;
    }
    
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        
        for (String word : words) {
            TrieNode current = root;
            for (char ch : word.toCharArray()) {
                int index = ch - 'a';
                if (current.children[index] == null) {
                    current.children[index] = new TrieNode();
                }
                current = current.children[index];
            }
            current.word = word;
        }
        
        return root;
    }
}

The solution uses a Trie data structure to efficiently search for multiple words simultaneously. It builds a trie from all the target words, then performs DFS on each cell of the board to search for valid words. The key insight is that we can avoid redundant searches by using the trie structure to prune paths early when a character doesn't exist in any remaining word prefix. We mark visited cells by temporarily changing their value to '#' and restore it afterward to allow reuse in different paths.

7. Complexity Analysis

Time Complexity: O(M × N × 4^L) where M and N are the dimensions of the board, and L is the maximum length of words in the dictionary.

The algorithm performs a DFS traversal from each cell on the board, which is O(M × N). For each starting position, in the worst case, we explore up to 4 directions recursively, and this can go as deep as the length of the longest word in our dictionary (L). Therefore, we get O(4^L) per starting position.

Space Complexity: O(K × L) where K is the number of words in the dictionary and L is the average length of words.

This space complexity comes from:

1. The Trie data structure that stores all the dictionary words, requiring O(K × L) space
2. The recursive call stack during DFS traversal, which in the worst case can go as deep as L (the maximum word length)
3. The result list that stores matching words, which in the worst case could contain all dictionary words

Why these bounds are correct:

• The time bound is tight because we explore every possible path from every starting position, and the branching factor of 4 (up, down, left, right) can grow exponentially with path length
• The space bound is optimal for this approach because we must store all dictionary words in a Trie and maintain the recursion stack depth

Optimality: This solution is near-optimal for the given constraints. The exponential factor in time complexity (4^L) is inherent to the problem structure - we must explore all possible paths of length up to L from each starting position. The space complexity is optimal for storing the dictionary and maintaining search state.

The solution avoids the naive O(M² × N²) approach that would check every word against every board position, reducing the time complexity from exponential in both dimensions to exponential only in word length.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty board: An empty 2D character array should return an empty result list. The solution must handle board.length == 0 or board[0].length == 0.
• Single cell board: A single character board should only return words that match that exact character.
• Empty word list: If words is empty, return an empty list without any processing.

Duplicate Values and Repeated States

• Duplicate words in input: If the same word appears multiple times in words, it should only appear once in the result list.
• Repeated character paths: The same word can be formed through different paths, but only one copy should appear in the result.
• Overlapping prefixes: Words like "a" and "aa" can share a prefix, so the solution must avoid counting shorter words when longer ones are found.

Boundary Conditions

• Single character words: Words of length 1 must be handled correctly, even when they're at the edge of the board.
• Board dimensions: Boards with one row or one column must be handled without index out-of-bounds errors.
• Word length vs board size: Words longer than the total number of cells should not be considered.

Common Implementation Mistakes

• Modifying input board: Using the board to mark visited cells without restoring them can cause incorrect results for subsequent words.
• Incorrect bounds checking: Failing to check row >= 0 && row < m && col >= 0 && col < n can lead to runtime exceptions.
• Not handling visited state properly: Reusing the same visited array or not resetting it between word searches can cause false positives.
• Incorrect trie traversal: Not properly advancing the trie node when a character matches, or failing to backtrack correctly.
• Missing duplicate filtering: Not ensuring that the same word doesn't get added multiple times to the result list.

Performance Pitfalls

• Recreating visited arrays: Creating a new visited array for each word search instead of reusing one can lead to unnecessary memory allocation.
• Inefficient trie lookup: Not leveraging the trie's structure properly can cause redundant character checks and slow down the search.
• Not pruning early: Failing to stop searching when a character doesn't exist in the trie can waste time on invalid paths.

9. Alternative Approaches

There are several alternative approaches to solving Word Search II, each with different trade-offs:

1. Trie + DFS without prefix optimization: Instead of building a complete trie, we could build a minimal trie structure that only stores words that exist as prefixes. This approach would still be O(m×n×4^L) in worst case but with better constants since we don't store all words.

2. Brute force with HashSet lookup: For each cell, we could generate all possible paths and check if any word exists in our dictionary using a HashSet lookup. This would be O(m×n×4^L) time complexity but with higher constants due to the dictionary lookups.

3. Bitmask-based approach: For small dictionaries, we could use bitmask operations to represent which words are still valid as we traverse. This is more of a micro-optimization and only beneficial for very specific constraints.

4. Multi-threaded DFS: For large grids, we could parallelize the search by having separate threads process different starting positions. This adds complexity and overhead but can provide performance benefits on multi-core systems.

The chosen solution using Trie + DFS is preferred because it provides optimal prefix pruning, reduces redundant computation through shared prefixes, and maintains clean separation between word existence checking and path exploration. The trie structure naturally handles the prefix matching efficiently, making it more scalable than alternatives that require full dictionary lookups at each step.

The main trade-off is between implementation complexity and performance gains - while alternatives like HashSet lookup might be simpler to implement, they don't provide the same level of prefix optimization that makes the Trie approach superior for this specific problem.

10. Test Cases

public class WordSearchIITests {
    
    @Test
    public void testBasicCase() {
        char[][] board = {
            {'o','a','a','n'},
            {'e','t','a','e'},
            {'i','h','k','r'},
            {'i','f','l','v'}
        };
        String[] words = {"oath","pea","eat","rain"};
        List<String> expected = Arrays.asList("oath", "eat");
        List<String> actual = new WordSearchII().findWords(board, words);
        Collections.sort(expected);
        Collections.sort(actual);
        assertEquals(expected, actual);
    }
    
    @Test
    public void testEmptyBoard() {
        char[][] board = {};
        String[] words = {"abc"};
        List<String> result = new WordSearchII().findWords(board, words);
        assertTrue(result.isEmpty());
    }
    
    @Test
    public void testSingleCellBoard() {
        char[][] board = {{'a'}};
        String[] words = {"a", "ab"};
        List<String> expected = Arrays.asList("a");
        List<String> actual = new WordSearchII().findWords(board, words);
        assertEquals(expected, actual);
    }
    
    @Test
    public void testDuplicateWords() {
        char[][] board = {
            {'a','b'},
            {'c','d'}
        };
        String[] words = {"ab", "ab"};
        List<String> expected = Arrays.asList("ab");
        List<String> actual = new WordSearchII().findWords(board, words);
        assertEquals(expected, actual);
    }
    
    @Test
    public void testNoMatches() {
        char[][] board = {
            {'x','y'},
            {'z','w'}
        };
        String[] words = {"abc", "def"};
        List<String> result = new WordSearchII().findWords(board, words);
        assertTrue(result.isEmpty());
    }
    
    @Test
    public void testWordNotFoundDueToPathRestriction() {
        char[][] board = {
            {'a','b','c'},
            {'d','e','f'},
            {'g','h','i'}
        };
        String[] words = {"abcf"};
        List<String> result = new WordSearchII().findWords(board, words);
        assertTrue(result.isEmpty());
    }
}

11. Final Summary

The core insight is to leverage a Trie data structure to efficiently search for multiple word patterns simultaneously by pruning the search space early when a prefix doesn't exist in our dictionary. This approach transforms the problem from checking each word independently (which would require repeated DFS traversals) into a single intelligent traversal that explores the board while maintaining a shared prefix structure.

The solution works by first building a Trie from all target words, then performing DFS from each board cell while maintaining the current path as a string and tracking which words have been found. When we reach a Trie node that marks the end of a word, we add it to our results and mark it as found to avoid duplicates.

This solution is efficient because it reduces redundant computations through the Trie's prefix property, allowing us to terminate early when a path doesn't lead to any valid word. The time complexity of O(M×N×4^L) where M×N is the board size and L is the maximum word length, and space complexity of O(K×L) where K is the total number of characters in all words, represents a significant improvement over naive approaches that would require O(K×M×N×4^L) time complexity.