Word Search II: Multiple Solutions and Complexity Analysis

Word Search II is a classic algorithmic problem frequently encountered in coding interviews and competitive programming. Given an m x n board of characters and a list of words, the task is to return all words from the list that can be found on the board. A word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a single word.

While the single-word version of the problem (Word Search I) can be solved with a straightforward backtracking DFS, the multi-word variant demands a more sophisticated approach. Naively running DFS for every word quickly becomes prohibitively expensive. This is where a Trie (prefix tree) combined with backtracking becomes essential, enabling efficient pruning of impossible search paths.

Why It Matters

Word Search II is more than an interview staple — it teaches several foundational concepts simultaneously:

Trie data structure: A natural fit for prefix-based lookups across many strings.
Backtracking with pruning: Knowing when to abandon a search path early saves enormous computation.
State management: Marking visited cells without extra memory by mutating the board in place.
Complexity trade-offs: Comparing brute force against optimized solutions builds intuition for algorithm design.

These skills transfer directly to real-world problems such as autocomplete systems, spell checkers, IP routing tables, and bioinformatics sequence matching.

Understanding the Problem

Consider the following board and word list:

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

The expected output is ["oath","eat"] because those words can be traced through adjacent cells without reusing any cell. The challenge is to find all such matches efficiently.

Solution 1: Brute Force DFS Per Word

The simplest approach iterates over each word and runs a DFS from every cell that matches the word's first character. This mirrors the solution to Word Search I, applied repeatedly.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    
    def dfs(r, c, index):
        if index == len(word):
            return True
        if (r < 0 or r >= rows or c < 0 or c >= cols 
            or board[r][c] != word[index]):
            return False
        
        temp = board[r][c]
        board[r][c] = '#'
        found = (dfs(r+1, c, index+1) or
                 dfs(r-1, c, index+1) or
                 dfs(r, c+1, index+1) or
                 dfs(r, c-1, index+1))
        board[r][c] = temp
        return found
    
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

def findWords_bruteforce(board, words):
    return [w for w in words if exist(board, w)]

This works but is inefficient. If there are k words of average length L, and the board is m x n, the worst-case time complexity is O(k * m * n * 4^L). For large inputs, this becomes intractable.

Solution 2: Trie + Backtracking (Optimal)

The key insight is that many words share common prefixes. By inserting all words into a Trie, we can explore the board once and simultaneously match all words whose prefixes align with the current path. When a cell's character does not extend any valid prefix, we prune immediately.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # stores the complete word at terminal node

def findWords(board, words):
    # Build the Trie
    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  # mark end of a valid word
    
    rows, cols = len(board), len(board[0])
    result = []
    
    def dfs(r, c, node):
        char = board[r][c]
        if char not in node.children:
            return
        
        next_node = node.children[char]
        if next_node.word:
            result.append(next_node.word)
            next_node.word = None  # avoid duplicate entries
        
        # Mark cell as visited
        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, next_node)
        
        # Restore cell
        board[r][c] = char
        
        # Optional optimization: prune leaf nodes
        if not next_node.children:
            del node.children[char]
    
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    
    return result

This solution explores the board once. At each cell, it descends into the Trie only if the character matches a child of the current Trie node. When a terminal node is reached, the corresponding word is added to the result. The in-place marking with # avoids allocating a separate visited matrix.

Complexity Analysis

Understanding the complexity of each approach is crucial for choosing the right tool.

Brute Force:

Time: O(k * m * n * 4^L), where k is the number of words, m x n is the board size, and L is the maximum word length.
Space: O(L) for the recursion stack per word search.

Trie + Backtracking:

Time: O(m * n * 4^L) in the worst case, but significantly better in practice due to prefix sharing and pruning. The Trie construction costs O(k * L).
Space: O(k * L) for the Trie, plus O(L) for the recursion stack.

The Trie approach eliminates the multiplicative k factor from the dominant term. When many words share prefixes — a common real-world scenario — the savings are dramatic. The pruning optimization that removes leaf Trie nodes after a word is found further reduces redundant exploration.

Best Practices

Mutate the board in place: Using a sentinel character like # avoids the overhead of a separate visited matrix and simplifies state management.
Prune Trie leaves: After collecting a word, delete its terminal node. If a node has no remaining children, remove it from its parent. This prevents revisiting dead branches.
Avoid duplicates: Setting node.word = None after collecting ensures each word appears only once, even if reachable through multiple paths.
Choose the smaller dimension for iteration: If the word list is tiny but the board is huge, brute force may suffice. If the word list is large with shared prefixes, the Trie approach wins decisively.
Consider word length limits: If all words are short (say, length 3 or less), the exponential factor 4^L is small, and even brute force can be acceptable.
Use iterative Trie building: Recursive Trie construction can hit recursion limits for very long word lists; an iterative approach is safer.

Variations and Extensions

Several variations test deeper understanding:

Diagonal movement allowed: Add four more direction vectors to the DFS neighbor loop.
Case-insensitive matching: Normalize all characters to lowercase during Trie construction and board traversal.
Return positions: Instead of returning words, return the list of coordinates forming each word. This requires tracking the path during DFS.
Streaming board: If the board changes dynamically, consider rebuilding the Trie or using a more advanced data structure like a suffix automaton.

Conclusion

Word Search II elegantly combines the Trie data structure with backtracking to solve a problem that would otherwise be computationally prohibitive. By sharing prefix exploration across all words and pruning aggressively, the Trie-based solution transforms an O(k * m * n * 4^L) brute force into a far more efficient O(m * n * 4^L) algorithm with strong practical performance. Mastering this problem deepens your understanding of when and how to apply Tries, how to manage backtracking state cleanly, and how to reason about complexity trade-offs — skills that are invaluable across a wide range of algorithmic challenges.