Solving Word Search II in Python: Step-by-Step Guide

Introduction to Word Search II

Word Search II is a classic algorithmic problem frequently encountered in coding interviews and competitive programming. Given a 2D 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 simpler Word Search I problem asks you to find a single word on the board, Word Search II scales this up to multiple words, demanding a more efficient approach than simply running a depth-first search (DFS) for each word independently.

Why This Problem Matters

Word Search II is an excellent test of your ability to combine multiple algorithmic concepts into a single, cohesive solution. It exercises your understanding of:

• Backtracking: Exploring paths on the board and undoing moves when a path fails.
• Trie data structure: Efficiently storing and searching a collection of words with shared prefixes.
• Graph traversal: Navigating a 2D grid using DFS with proper boundary and visited-state management.
• Time complexity optimization: Recognizing when a naive solution is too slow and applying the right data structure to reduce redundant work.

In real-world applications, similar patterns appear in autocomplete systems, spell checkers, dictionary lookups, and any scenario where you need to match strings against a structured grid or sequence of characters.

Understanding the Problem

Let's formalize the problem. You are given:

• A m x n board of characters.
• A list of strings called words.

You must return all words from words that exist on the board. A word exists if you can trace it by moving to adjacent cells (up, down, left, right) without reusing any cell within the same word's path.

Example

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 ["eat","oath"] because these two words can be traced on the board, while "pea" and "rain" cannot.

The Naive Approach and Its Limitations

The most straightforward solution is to iterate over each word and run a DFS from every cell on the board to check if that word exists. For each word of length L, the DFS explores up to 4^L paths. With N words, the total time complexity becomes O(N * m * n * 4^L).

This approach performs redundant work. If two words share a common prefix, such as "apple" and "apply", the DFS will explore the same initial paths twice. When the word list is large or contains many overlapping prefixes, this inefficiency becomes a serious bottleneck.

Introducing the Trie

A Trie (pronounced "try") is a tree-like data structure that stores a dynamic set of strings, where each node represents a single character. Tries excel at prefix-based operations. By inserting all words into a Trie before searching, we can explore the board once and simultaneously check all words for matches.

The key insight is this: instead of searching for each word separately, we traverse the board and walk down the Trie at the same time. If the current cell's character does not match any child of the current Trie node, we prune that branch immediately. This dramatically reduces the search space.

Trie Node Structure

Here is a simple Trie node implementation in Python:

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

Using a dictionary for children allows us to handle any character set efficiently. The word attribute is set to the full word string when a node marks the end of a valid word. This avoids reconstructing the word from the path during traversal.

Building the Trie

Before searching the board, we insert every word from the input list into the Trie:

def build_trie(words):
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word = word
    return root

Each character of each word is inserted as a node. When we reach the end of a word, we store the word itself in the terminal node. This storage strategy lets us collect a found word in constant time during the board search.

Searching the Board with Backtracking

With the Trie built, we now traverse every cell on the board. From each cell, we initiate a DFS that simultaneously walks the Trie. The algorithm proceeds as follows:

• If the current cell's character is not a child of the current Trie node, stop exploring this path.
• If the current Trie node has a stored word, add it to the results.
• Mark the current cell as visited to prevent reuse within the same path.
• Recursively explore all four adjacent cells.
• Restore the cell's original character after recursion (backtracking).

Complete Implementation

Here is the full solution combining the Trie and the backtracking search:

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


class Solution:
    def findWords(self, board, words):
        # Step 1: Build the Trie from the word list
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word

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

        def dfs(r, c, node):
            char = board[r][c]

            # If the character is not in the current Trie node's children, prune
            if char not in node.children:
                return

            next_node = node.children[char]

            # If we found a complete word, record it
            if next_node.word is not None:
                result.append(next_node.word)
                next_node.word = None  # Avoid duplicate entries

            # Mark the cell as visited
            board[r][c] = '#'

            # Explore all four directions
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    dfs(nr, nc, next_node)

            # Backtrack: restore the cell
            board[r][c] = char

            # Optimization: remove leaf nodes to prune future searches
            if not next_node.children:
                node.children.pop(char)

        # Step 2: Start DFS from every cell on the board
        for i in range(rows):
            for j in range(cols):
                dfs(i, j, root)

        return result

How the Code Works

The findWords method first builds the Trie. Then, for every cell on the board, it calls dfs with the root of the Trie. Inside dfs, the method checks whether the current cell's character leads anywhere in the Trie. If it does, and if that Trie node marks the end of a word, the word is added to the result list and the word reference is cleared to prevent duplicates.

The visited state is managed by temporarily replacing the cell's character with a sentinel value '#'. After exploring all four directions, the original character is restored. This in-place marking avoids the overhead of maintaining a separate visited matrix.

The final optimization removes leaf nodes from the Trie after all their children have been explored. Once a Trie node has no children and its word has been collected, it is safe to delete it. This prevents the algorithm from re-exploring dead-end paths from other starting cells on the board.

Complexity Analysis

Let m and n be the dimensions of the board, L be the maximum length of any word, and N be the number of words.

• Time complexity: O(m * n * 4^L) in the worst case, but the Trie-based pruning makes this much faster in practice. The Trie reduces redundant exploration by sharing prefixes across words.
• Space complexity: O(N * L) for the Trie, plus O(L) for the recursion stack during DFS.

In contrast, the naive approach without a Trie has a time complexity of O(N * m * n * 4^L), which is significantly worse when N is large.

Best Practices

1. Prune the Trie Aggressively

Removing leaf nodes after exploration is one of the most impactful optimizations. Once a word is found and its node has no remaining children, deleting it prevents other DFS paths from wastefully descending into a branch that can no longer yield new results.

2. Avoid Duplicate Results

Set next_node.word = None after collecting a word. This ensures that if the same word can be formed through multiple paths on the board, it appears only once in the result. Using a set for results is another option, but clearing the word reference is more memory efficient.

3. Use In-Place Visited Marking

Instead of allocating a separate 2D visited array, temporarily modify the board cell. This saves memory and avoids the overhead of resetting a visited matrix after each DFS. Just remember to restore the original character during backtracking.

4. Handle Edge Cases

Always validate inputs. Check for empty boards, empty word lists, and words longer than the total number of cells on the board. A word longer than m * n can never be found and can be skipped during Trie construction.

5. Choose Directions Wisely

Defining the four directions as a list of tuples keeps the code clean and easy to modify. If diagonal movement were allowed, you would simply add four more tuples to the directions list.

Testing the Solution

Here is a test script that validates the implementation against the example input:

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

    solution = Solution()
    found_words = solution.findWords(board, words)
    print("Found words:", found_words)
    # Expected output: ['oath', 'eat'] (order may vary)

When you run this script, the output should contain both "oath" and "eat". The order may differ depending on the traversal sequence, but both words must be present and no others.

Common Pitfalls

• Forgetting to backtrack: If you do not restore the cell's character after recursion, subsequent DFS calls from other starting points will see corrupted board state and produce incorrect results.
• Not clearing found words: Without setting word = None after collection, duplicate words may appear in the output if multiple paths form the same word.
• Ignoring boundary checks: Always verify that the next cell coordinates are within the board before making a recursive call.
• Using a set for results without clearing Trie nodes: While a set prevents duplicates, it does not provide the pruning benefit of removing explored Trie branches, leading to slower performance.

Conclusion

Solving Word Search II efficiently requires combining a Trie with backtracking DFS. The Trie eliminates redundant prefix exploration, while backtracking with in-place visited marking keeps memory usage low. By pruning the Trie during traversal and clearing found words to avoid duplicates, you can achieve a solution that handles large boards and word lists gracefully. This problem is a powerful demonstration of how choosing the right data structure transforms an intractable brute-force approach into an elegant and efficient algorithm, and mastering it will strengthen your ability to tackle a wide range of string and grid-based challenges in technical interviews and beyond.