Word Search II

Difficulty: Hard Source: NeetCode

Problem

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must 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 word.

Example 1: Input: 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"]

Constraints:

• m == board.length, n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter
• 1 <= words.length <= 3 * 10^4
• 1 <= words[i].length <= 10
• All words in words are unique

Prerequisites

Before attempting this problem, you should be comfortable with:

• Trie (Prefix Tree) — central to the optimal solution; building and traversing a trie
• DFS / Backtracking — exploring the board path recursively while unmarking visited cells on backtrack
• Word Search I (LeetCode 79) — this problem is a natural extension of it

1. Brute Force (Word Search I for each word)

Intuition

Run the Word Search I algorithm independently for each word in words. For each word, try starting a DFS from every cell on the board. This is straightforward but scales poorly — if you have thousands of words, you do thousands of full board sweeps.

Algorithm

1. For each word in words:
   • For each cell (r, c) on the board, run DFS to check if word can be formed starting here.
   • If yes, add word to results.
2. Return results.

Solution

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    rows, cols = len(board), len(board[0])
    result = []

    def dfs(r, c, i, word):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[i]:
            return False
        tmp = board[r][c]
        board[r][c] = '#'  # mark visited
        found = (dfs(r+1, c, i+1, word) or dfs(r-1, c, i+1, word) or
                 dfs(r, c+1, i+1, word) or dfs(r, c-1, i+1, word))
        board[r][c] = tmp  # restore
        return found

    for word in words:
        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0, word):
                    result.append(word)
                    break
            else:
                continue
            break

    return result


board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
print(findWords(board, ["oath","pea","eat","rain"]))  # ['oath', 'eat']

Complexity

• Time: O(W * M * N * 4^L) where W = number of words, L = max word length
• Space: O(L) recursion stack per word

2. Trie + Single Board DFS

Intuition

Instead of searching for each word separately, build a trie from all words and run a single DFS over the board. At each cell, follow the trie character by character. If the current cell’s letter doesn’t exist as a child in the current trie node, prune immediately — we know no word starts that way. When we reach a node with is_end = True, we’ve found a word; record it and mark is_end = False to avoid duplicates. This shares prefix work across all words and prunes dead ends early.

Algorithm

1. Build a trie from words. Each node also stores the word string at is_end nodes (easier than reconstructing).
2. DFS over every board cell (r, c) as a potential starting point.
3. In the DFS, given node (current trie node) and position (r, c):
   • If board[r][c] not in node.children, return.
   • Move to next_node = node.children[board[r][c]].
   • If next_node.word, add it to results and clear next_node.word (dedup).
   • Mark cell visited, recurse into 4 neighbors, unmark on backtrack.
4. Optional: prune empty trie nodes after finding words (pruning optimization).

Solution

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


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

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

    def dfs(r, c, node):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        ch = board[r][c]
        if ch == '#' or ch not in node.children:
            return

        next_node = node.children[ch]

        if next_node.word:
            result.append(next_node.word)
            next_node.word = None  # prevent duplicate results

        board[r][c] = '#'  # mark visited
        dfs(r + 1, c, next_node)
        dfs(r - 1, c, next_node)
        dfs(r, c + 1, next_node)
        dfs(r, c - 1, next_node)
        board[r][c] = ch   # restore

        # Prune: remove leaf nodes that are done
        if not next_node.children:
            del node.children[ch]

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

    return result


board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
print(sorted(findWords(board, ["oath","pea","eat","rain"])))  # ['eat', 'oath']

board2 = [["a","b"],["c","d"]]
print(findWords(board2, ["abdc","abcd","adcb"]))  # ['abdc', 'abcd']

Complexity

• Time: O(M * N * 4^L + W * L) — board DFS with pruning + trie build
• Space: O(W * L) for trie, O(L) recursion depth

Common Pitfalls

Not deduplicating found words. The same word could be found via multiple paths on the board. Setting next_node.word = None after finding it ensures you only add it once.

Forgetting to restore board cells. After DFS backtracks, you must undo the '#' marker. If you forget, subsequent DFS calls will see cells as already visited and miss valid paths.

The pruning optimization. Removing empty leaf nodes (del node.children[ch]) is optional but significantly speeds up the solution on large inputs, because it prevents re-entering exhausted trie branches. Don’t skip it in a real interview.

Starting the search from every cell. Don’t only start from cells that match the first character of some word — let the trie check handle that, since the condition ch not in node.children handles the pruning at the root level naturally.