Word Search with Trie and Backtracking

1. The Strategy: Why a Trie with Backtracking is Essential

Let's quickly refresh our memory on the problem. We have a 2D grid of characters and a list of words. We need to find all the words from the list that can be formed by traversing adjacent cells (horizontally or vertically) without reusing a cell for a single word.

A brute-force approach, where we search the entire grid for each word one-by-one, is highly inefficient. The power of the optimal solution lies in reversing the logic: we traverse the grid and use a Trie built from our dictionary to see which words we can form.

To understand this better, let's consult a resource that clearly lays out the algorithm.

As the article explains, the core idea is to perform a Depth-First Search (DFS) from every cell, but at each step of the search, we check if our current path forms a valid prefix in the Trie. If not, we backtrack immediately. This avoids exploring countless paths that could never lead to a valid word.

2. A Detailed Implementation Walkthrough

Let's get practical and walk through a complete Java implementation. Your background in building complex systems like the AI Sentry Gun shows you're comfortable with integrating different components. Here, our components are the Trie data structure and the DFS backtracking algorithm.

The overall process is:

1. Build the Trie: Populate a Trie with all the words from the dictionary.
2. Iterate and Search: Loop through every cell of the board and launch a DFS from each one.
3. Collect Results: Use a List or Set to store the words found. A Set is often preferred to automatically handle cases where a word can be formed in multiple ways.

Let's watch a video that walks through this entire flow, from building the Trie to the final backtracking logic.

The Code, Deconstructed

Drawing from the video and the takeuforward.org article, let's assemble the Java code.

Part 1: The TrieNode and Trie Construction

This is similar to what we've built before, but with the small, useful addition of storing the full word in the node that marks its end.

class Solution {
    // Inner class for the Trie node
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null; // Store the word if this node is an endpoint
    }

    // Method to insert words into the Trie
    private void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.word = word;
    }
    
    // ... rest of the solution methods
}

Part 2: The Main findWords Function

This function orchestrates the process. It's the "manager" that sets up the Trie and tells the DFS "workers" where to start searching.

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

    List<String> result = new ArrayList<>();
    int rows = board.length;
    int cols = board[0].length;

    // Start a DFS from every cell on the board
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dfs(board, i, j, root, result);
        }
    }

    return result;
}

Part 3: The dfs Backtracking Function

This is where the magic happens. This recursive function explores a path, guided by the Trie.

private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
    // --- Base Cases (Pruning Conditions) ---
    // 1. Check for out of bounds
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
        return;
    }
    
    char c = board[i][j];

    // 2. Check if path is invalid (already visited or no such prefix in Trie)
    if (c == '#' || node.children[c - 'a'] == null) {
        return;
    }

    // --- Move Forward ---
    node = node.children[c - 'a'];

    // --- Check for a Found Word ---
    if (node.word != null) {
        result.add(node.word);
        // Optimization: Prevent this word from being added again.
        node.word = null; 
    }

    // --- Backtracking Logic ---
    // 1. Make a change (mark as visited)
    board[i][j] = '#';

    // 2. Recurse (explore neighbors)
    dfs(board, i + 1, j, node, result); // Down
    dfs(board, i - 1, j, node, result); // Up
    dfs(board, i, j + 1, node, result); // Right
    dfs(board, i, j - 1, node, result); // Left

    // 3. Undo the change (backtrack)
    board[i][j] = c;
}

3. Key Optimizations and Common Pitfalls

Mastering an algorithm for an interview setting means knowing not just the base case, but also the common optimizations and potential traps.

Optimization: Pruning the Trie

In the dfs function above, notice this line: node.word = null;. This is a crucial optimization. Once we find a word (e.g., "oath"), we add it to our results and then effectively "remove" it from the Trie by nullifying the word field.

Why is this important?

1. Prevents Duplicates: If the word "oath" could be formed two different ways on the board, we would add it to our result list twice without this optimization.
2. Minor Performance Gain: In some cases, this can lead to earlier pruning of the Trie itself (more on this in advanced scenarios).

Common Pitfall: Incorrect Backtracking

The single most common bug in this type of problem is forgetting to backtrack correctly. If you mark a cell as visited (board[i][j] = '#';) but fail to restore it (board[i][j] = c;) after the recursive calls return, that cell becomes permanently unavailable for any other search paths originating from other starting cells.

4. Complexity Analysis

For someone with your background, understanding the performance characteristics is key.

To summarize the analysis:

• Time Complexity: O(M * N * 4 * 3^(L-1)) + O(W * L_avg)

  • W * L_avg is the time to build the Trie, where W is the number of words and L_avg is their average length.
  • M * N is the number of cells on the board. From each cell, we start a DFS.
  • The term 4 * 3^(L-1) represents the maximum number of nodes in a search path of length L (the length of the longest word). We have 4 choices for the first move and up to 3 for subsequent moves (since we can't go back). In practice, the Trie prunes this search space so dramatically that the performance is much better than this worst-case bound suggests.

• Space Complexity: O(W * L_avg) + O(L)

  • W * L_avg is the space required to store the Trie itself.
  • O(L) is the space used by the recursion stack during the DFS, which is bounded by the length of the longest word, L.

Conclusion

You have now completed a deep dive into one of the most classic and practical combinations of data structures and algorithms. By combining the efficient prefix-checking of a Trie with the exhaustive path-finding of backtracking, we can solve a complex problem elegantly and efficiently.

Key Takeaways:

• The Pattern: For problems involving searching a grid for multiple dictionary words, the Trie + Backtracking pattern is the go-to optimal solution.
• Trie's Role: The Trie's primary job is to enable aggressive pruning of the search space.
• Backtracking Mechanics: The make change -> recurse -> undo change pattern is fundamental. In this case, it involves temporarily modifying the board to mark visited cells.
• Optimization: Pruning the Trie by nullifying found words is a simple but effective way to handle duplicates and is a detail interviewers look for.

Preview of the Next Lesson:
We've just tackled a fairly advanced backtracking problem where the Trie guided our choices. To further strengthen your skills for interviews and competitive programming, we're going to step back slightly and build up your backtracking toolkit from the fundamentals. In the next lesson, we'll start with a foundational backtracking problem: generating all subsets of a set using a recursive approach. This will help you master the core recursive structure of backtracking in a cleaner, more isolated context.