9 minute read

“Don’t look for one needle in a haystack. Magnetize the hay to find all needles at once.”

TL;DR

Word Search II finds all dictionary words on a character grid by flipping the search: instead of searching for each word, build a Trie from the dictionary and let the grid DFS be guided by the Trie. At each cell, check if the current character is a valid Trie child before continuing. Incrementally prune found words from the Trie to shrink the search space over time. The same “walk a Trie in lockstep with the search and drop dead prefixes” pattern shows up in typeahead systems and in lexicon-constrained speech decoding, and the grid DFS reuses the mark, explore, unmark template from N-Queens.

1. Problem Statement

This is the “Boss Level” of grid-based search problems. Given an m x n board of characters and a list of strings words, return all words on the board.

Rules:

  1. Each word must be constructed from letters of sequentially adjacent cells (horizontally or vertically neighboring).
  2. The same letter cell may not be used more than once in a word.
  3. The output should contain all unique words found.

Example:

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"]

Note: “pea” is not present. “rain” is not present.


2. Understanding the Problem

2.1 The Naive vs. Optimized Mindset

  • Word Search I: Find one word. We iterate the grid and run DFS for that word.
  • Word Search II: Find K words (LeetCode allows K up to 30,000).

If we define M, N as grid dimensions and L as max word length:

  • Naive Approach: For each word, scan grid. Total Time: O(K × M × N × 4^L).
  • This is horribly inefficient. We are visiting the same cells (0,0) ‘o’ -> (0,1) ‘a’ thousands of times, once for “oath”, once for “oats”, once for “oatmeal”…

2.2 The Inversion of Control

Instead of “For each word, search the grid”, we flip it: “For each path in the grid, does it form any word?”

To support this query (“Does this prefix exist in my list?”), we need a Trie (Prefix Tree).


3. Approach 1: Naive (Repeated DFS, don’t do this)

Run the solution for “Word Search I” inside a loop. It works, but it is far too slow for large word lists because it ignores the shared prefixes of the dictionary words. Mention it only as the baseline you are about to improve.


4. Approach 2: Backtracking with Trie

We build a Trie from the dictionary words. Then we start DFS from every cell in the grid. As we traverse the grid (e.g., o -> a -> t), we move a pointer down the Trie.

Key Logic

  1. Build Trie: Insert all words into Trie. Mark leaf nodes with the actual word.
  2. Grid DFS:
    • Start at (r, c).
    • Check if board[r][c] is a child of Current_Trie_Node.
    • If Yes: Move to child. Mark visited. Recurse.
    • If No: Stop (Pruning).
  3. Optimization (Leaf Pruning):
    • Once we find a word like “oath”, we add it to results.
    • Crucial: We should remove “oath” from the Trie (or mark it found) so we don’t find it again via a different path.
    • Even better: If a node has no children after finding a word, delete the node. This progressively shrinks the search space!

5. Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None # Stores the word at the leaf node

class Solution:
    def findWords(self, board, words):
        # 1. Build the Trie
        root = TrieNode()
        for w in words:
            node = root
            for char in w:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = w # End of word
            
        self.res = []
        rows, cols = len(board), len(board[0])
        
        def dfs(r, c, parent_node):
            letter = board[r][c]
            curr_node = parent_node.children[letter]
            
            # Check for match
            if curr_node.word:
                self.res.append(curr_node.word)
                curr_node.word = None # De-duplicate: Ensure we don't add it again
            
            # DFS Traversal logic
            board[r][c] = '#' # Mark visited
            
            for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
                nr, nc = r+dr, c+dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if board[nr][nc] in curr_node.children:
                        dfs(nr, nc, curr_node)
            
            board[r][c] = letter # Backtrack
            
            # 3. Optimization: Incremental Pruning
            # If leaf node and no word, prune it to optimize future searches
            if not curr_node.children:
                del parent_node.children[letter]

        # Trigger DFS
        for r in range(rows):
            for c in range(cols):
                if board[r][c] in root.children:
                    dfs(r, c, root)
                    
        return self.res

6. Testing Strategy

Test Case 1: Prefix shared

Words: ["oath", "oat"]. Board: Contains o -> a -> t -> h.

  • DFS reaches ‘t’. Finds “oat”. Adds to result. Removes word marker.
  • DFS continues to ‘h’. Finds “oath”. Adds to result.
  • Backtrack.

Test Case 2: No match

Words: ["abcd"]. Board: ['a', 'b', 'x', 'd'].

  • DFS matches a -> b.
  • Next neighbor x is not in Trie child of b.
  • Stop immediately. (This shows the power of Trie pruning vs Naive).

7. Complexity Analysis

  • Time: O(M × N × 4 × 3^(L-1)), usually quoted as O(M × N × 4^L).
    • From each of the M × N starting cells, the first step has 4 directions and every later step at most 3 (we never step back onto the cell we came from), for up to L steps.
    • The Trie makes this much faster in practice because branches die as soon as the prefix leaves the dictionary, and leaf pruning removes words once they are found.
  • Space: O(K × L) for Trie storage (K words, length L), plus O(L) recursion depth.

8. Production Considerations

  1. Thread Safety: In a real “Boggle Solver” server, building the Trie is a one-time startup cost and the DFS is per-request, so the shared Trie must be read-only during requests. The implementation above is not read-only: it clears word markers, deletes pruned nodes and writes '#' into the board. In a server, either give each request its own copy of the Trie and board, or skip the pruning and record found words in a per-request set.
  2. Memory: A pointer-based Trie over a large dictionary uses many times more memory than the word list itself, especially in Python where every node is an object with its own dict. A DAWG (Directed Acyclic Word Graph) shares suffixes as well as prefixes (e.g., “-ing”), which shrinks it considerably.

9. Connections to ML Systems

The reusable idea is not the grid but the pattern: advance a Trie pointer in lockstep with another search, and abandon a branch the moment its prefix is not in the Trie.

  • Typeahead and autocomplete: walk the Trie along the characters the user has typed, then collect the best completions below that node. Production systems precompute top-K completions per node so the lookup stays fast; see Trie-Based Search Systems.
  • Lexicon-constrained speech decoding: an ASR decoder that must emit dictionary words can store the vocabulary (or its pronunciations) in a prefix tree and keep only the hypotheses whose partial word is still a valid prefix. Classic large-vocabulary decoders used tree-structured lexicons for exactly this, and lexicon-constrained CTC beam search does the same today. Hypotheses outside the Trie are pruned just like dead grid paths here.
  • Phonetic search: the same structure built over phoneme sequences instead of letters lets you match words by sound; see Phonetic Search.

10. Interview Strategy

  1. Start with Naive: Briefly mention “I could just run DFS for each word”, then immediately pivot. “But that’s inefficient because…”
  2. Draw the Trie: Show how “ant” and “and” share the “an” node.
  3. Explain Pruning: This is the differentiator. “If I remove the leaf node after finding a word, the Trie gets smaller.” This shows senior-level optimization thinking.

11. Key Takeaways

  1. State Machines: A Trie acts as a State Machine for the DFS. “Am I allowed to step on ‘X’?” depends on my current Trie node.
  2. Preprocessing wins: Spend O(total characters in words) building a Trie to avoid repeating the exponential search once per word.
  3. Backtracking Template: Mark -> Explore -> Unmark is the universal pattern.

FAQ

Why is a Trie essential for Word Search II?

A Trie lets you check whether the current grid path forms a valid prefix of any dictionary word in O(1) per step. Without it, you would repeat DFS for each word independently, wasting enormous time on shared prefixes like “oat” and “oath” that could be checked once.

How does incremental pruning optimize Word Search II?

After finding a word, remove it from the Trie and delete any leaf nodes with no remaining children. This progressively shrinks the Trie, reducing future DFS branches and making the algorithm faster as it discovers more words.

What is the time complexity of Word Search II with a Trie?

The worst-case time is O(M x N x 4^L) where M and N are grid dimensions and L is the max word length. However, Trie pruning makes the average case dramatically faster by cutting off invalid path explorations early.

How does Word Search II relate to typeahead search systems?

Word Search II uses the same Trie-driven search pattern found in typeahead and autocomplete systems. The Trie stores the product catalog or dictionary, user input or grid traversal drives the exploration, and prefix matching efficiently finds all valid completions.