The O(n) Club: Word Search II: Why Your Brute Force Solution Needs an Intervention

The O(n) Club: Word Search II—Why Your Brute Force Solution Needs an Intervention

⚡ TL;DR

Want to find every dictionary word in a letter grid, LeetCode 212-style? You COULD DFS every word (and regret it instantly), or you could build a Trie and let backtracking do the work. Enjoy fewer tears. Example of brute-force pain:

// Don't do this to your CPU:
for (String word : words) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (dfs(board, i, j, word, 0)) {
                result.add(word);
            }
        }
    }
}
// Welcome to exponential runtime!

🧠 How Devs Usually Mess This Up

Ah, classic panic: “Let’s just DFS every word from every cell. How bad could it be?” Hope you enjoy O(N * m * n * L) performance—because your recruiter won’t. Brute force on a big grid means you’ll see your reflection in a stale coffee cup before seeing an answer.

🔍 What’s Actually Going On

The board is a graph. Each cell is like a little chatty node that can talk (up, down, left, right—no diagonals, we’re not animals) to its neighbors. But words love prefixes and Tries love words. So, build a Trie for all words once, and backtrack across the board—jumping out early if a path isn’t a live prefix in your Trie. Fewer wasted steps, more jaw-dropping runtime.

🛠️ PseudoCode

  • Build a Trie from words
    • insert(word): for each letter, create node if missing; mark word ends.
  • Loop through every cell on the board
    • for each (i, j): backtrack(i, j, rootTrieNode)
  • While backtracking:
    • If cell is out of bounds or already visited—stop.
    • If Trie node has word—add to results, then nuke node.word to avoid repeats.
    • Check all 4 directions, keep going if the next letter exists in the Trie path.
    • Mark cell as visited (like writing on your hand), then clean up on return.

💻 The Code

// Standard Java magic
class Solution {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }
     public List
<string> findWords(char[][] board, String[] words) {
        List
<string> found = new ArrayList<>();
        TrieNode root = buildTrie(words);
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root, found);
            }
        }
        return found;
    }
     private void dfs(char[][] board, int i, int j, TrieNode node, List
<string> found) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) return;
        char c = board[i][j];
        if (c == '#' || node.children[c - 'a'] == null) return;
        node = node.children[c - 'a'];
        if (node.word != null) {
            found.add(node.word);
            node.word = null; // No repeats in this club
        }
        board[i][j] = '#';
        dfs(board, i - 1, j, node, found);
        dfs(board, i + 1, j, node, found);
        dfs(board, i, j - 1, node, found);
        dfs(board, i, j + 1, node, found);
        board[i][j] = c;
    }
     private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null)
                    node.children[idx] = new TrieNode();
                node = node.children[idx];
            }
            node.word = w;
        }
        return root;
    }
}
</string></string></string>

⚠️ Pitfalls, Traps & Runtime Smacks

  • Don’t revisit the same cell in one path unless you’re writing an infinite loop demo.
  • Null out the Trie node’s word string or your result list will get real spammy, real quick.
  • Cloning the board or using a visited[][]? Sure, if you love wasting space. Mutate and un-mutate letters for efficiency (just don’t forget to clean up after).
  • Trie + backtracking: Acceptable. Brute force? Grab a pillow, it’s O(N * m * n * L).

🧠 Interviewer Brain-Tattoo

If you’re searching for more than one word, build a Trie—save time, dignity, and potentially a recruiter’s faith in humanity. Remember: “Great devs don’t brute force what a Trie can prune.” (Or: Friends don’t let friends DFS every word.)

Previous Article

The Mutex Club: User vs Kernel Threads: Know the Difference

Next Article

The Mutex Club: Thread Safety Without the Pain