Word Search II: Trie-Powered Board Search

You are given an m x n board of characters and a list of words. Return all words that can be found on the board, where each word is built from letters of sequentially adjacent cells (up, down, left, right) and no cell is reused within a single word.

This is LeetCode 212: Word Search II, and it is one of the best problems for combining two important patterns: trie construction and grid DFS backtracking. If you solved Word Search I with plain backtracking, Word Search II asks you to do something smarter.

Why the naive approach is too slow

The brute force idea is simple: run the Word Search I DFS for each word in the list. If you have k words, each of length L, on an m x n board, the cost is O(k * m * n * 4^L). When the word list has thousands of entries, this blows up.

The problem is that each search starts from scratch. You scan the entire board for "oath", then scan the entire board for "eat", then again for "rain". Most of that work is redundant. Adjacent cells get explored over and over for different words that share the same prefix.

The fix is to search for all words at the same time. Build a trie from the word list, then run a single DFS pass over the board. At each cell, you check the trie to see if the current path matches any prefix. If the trie says "no word starts with these letters," you prune the entire branch immediately.

The trie + DFS approach

The algorithm has two phases:

Phase 1: Build the trie. Insert every word from the word list into a trie. Each node stores a dictionary of children and an optional word field. When you finish inserting a word, store the full word string at the last node. This avoids reconstructing the word from the path later.

Phase 2: DFS from every cell. For each cell on the board, check if the cell's letter exists as a child of the trie root. If so, start a DFS that walks the board and the trie simultaneously. At each step, the board tells you which letters are adjacent, and the trie tells you which letters could continue a valid word. If the current trie node has a word field, you found a complete word. Add it to the results.

The key insight is that one DFS pass handles all words at once. You never search for individual words. The trie does the multiplexing for you.

Python solution

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word = w

    rows, cols = len(board), len(board[0])
    result = []

    def dfs(r, c, node):
        ch = board[r][c]
        if ch not in node.children:
            return
        child = node.children[ch]

        if child.word:
            result.append(child.word)
            child.word = None

        board[r][c] = "#"
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                dfs(nr, nc, child)
        board[r][c] = ch

        if not child.children:
            del node.children[ch]

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)

    return result

Let's walk through the key parts.

Trie construction is the first loop. For each word, walk through the trie creating nodes as needed. At the last character, store the entire word string in node.word. This makes collecting results easy: when the DFS hits a node with word set, just append it.

The DFS takes a board position (r, c) and a trie node. It checks if the current cell's character is a child of the trie node. If not, return immediately. This is the pruning step: the trie tells us no word in our list continues with this character, so there is no point exploring further.

Finding a word happens when child.word is not None. We add the word to results and set child.word = None to prevent duplicates. The board might contain multiple paths that spell the same word, but we only want it in the output once.

Backtracking is the same choose-explore-unchoose pattern from Word Search I. Replace the cell with "#" before exploring neighbors, restore it afterward. This prevents the DFS from revisiting cells within a single path.

Trie pruning optimization

The last two lines of the DFS function are the pruning optimization:

if not child.children:
    del node.children[ch]

After exploring all paths through a trie node, if that node has no remaining children, delete it from its parent. This happens naturally after you find a word: the leaf node's word field gets cleared, and if it has no children, it is dead weight. Removing it means future DFS passes skip this branch entirely.

This matters for performance. Without pruning, the trie stays the same size throughout the search. With pruning, the trie shrinks as words are found. If your word list has many words that share prefixes, the trie can shrink dramatically after finding just a few words.

Visual walkthrough

Let's trace through a small example. The board is 3x3, and the word list is ["eat", "eta"]. Watch how the trie and board work together, and how pruning removes found words.

Notice how the DFS never explores paths that the trie does not support. If a cell's letter is not a child of the current trie node, the DFS returns immediately. This is far more efficient than running a separate search for each word.

Complexity analysis

Time is O(m * n * 4^L), where m * n is the board size and L is the maximum word length. For each of the m * n cells, the DFS can branch into 4 directions at each of L levels. In practice, trie pruning and character mismatches cut this down significantly. The key improvement over the naive approach is that you pay this cost once for all words, not once per word.

Space is O(k * L) for the trie, where k is the number of words and L is the average word length. The recursion stack adds O(L). The trie dominates. In the worst case (no shared prefixes), you store every character of every word. In the best case (all words share a long prefix), the trie is much smaller than the total character count.

Building blocks

This problem combines two reusable patterns that CodeBricks drills independently:

1. Trie structure (insert and traverse)

The trie is the data structure that makes multi-word search possible. The same insert-and-walk pattern appears in Implement Trie, autocomplete systems, and any problem where you need to check prefixes efficiently. The building block is: create a TrieNode with a children dictionary, insert words character by character, and walk the trie to check membership or prefixes.

2. Grid DFS backtracking

The DFS with choose-explore-unchoose is identical to Word Search I. Mark the cell, explore neighbors, restore the cell. The difference in Word Search II is that the trie guides which neighbors to explore. Instead of comparing against a fixed target string, you check the trie node's children. The backtracking skeleton itself is exactly the same.

When you can write both pieces from memory, combining them for Word Search II is natural. The trie replaces the target string. The DFS stays the same.

Edge cases

Before submitting, check these:

• Single cell board: board = [["a"]], words = ["a"]. The DFS should find it immediately with no neighbor exploration.
• Duplicate letters on the board: board = [["a","a"],["a","a"]], words = ["aaaa"]. The path must snake through all four cells without reuse. Tests that your visited marking works.
• Word is a prefix of another: words = ["eat", "eater"]. Finding "eat" should not prevent finding "eater". The pruning step only removes leaf nodes, so the path to "eater" stays intact.
• No words found: all words are absent from the board. The DFS should terminate quickly due to trie pruning at the first character.
• Overlapping paths: two words share a starting path but diverge. The backtracking must correctly unchoose cells so both paths can be explored.

From understanding to recall

You have seen how the trie and DFS work together. You understand the pruning optimization and why it matters. But can you write the TrieNode class, the insert loop, and the DFS function from scratch under time pressure?

That is where most people get stuck. The individual pieces are not complex. The trie insert is a few lines. The DFS backtracking is the same skeleton you have seen before. But assembling them correctly, with the pruning step, the word field trick, and the "#" cell marking, requires fluent recall of both building blocks.

Spaced repetition is the most effective way to build that recall. You practice writing the trie insert pattern and the grid DFS backtracking pattern separately, at increasing intervals. After a few rounds, each piece flows automatically. When you see Word Search II in an interview, you recognize the two building blocks, combine them, and write the solution without hesitation.

Related posts

• Word Search - The single-word version using pure grid backtracking. Master this first before tackling Word Search II.
• Implement Trie - How to build a trie from scratch. The same TrieNode structure powers the Word Search II solution.

CodeBricks breaks Word Search II into its trie-structure and grid-DFS-backtracking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a trie backtracking problem shows up in your interview, you do not think about it. You just write it.