Word Search II

Signal

Searching a grid for one word is a single DFS with backtracking. Searching for many words at once is the same DFS — but running it once per word wastes work re-exploring shared prefixes over and over. Whenever a board search needs to match against a whole dictionary of targets simultaneously, build one trie from all the words first and walk the trie alongside the DFS, so shared prefixes are explored exactly once and dead branches get pruned immediately.

Approach

Insert every target word into a trie, storing the full word on its terminal node (instead of just a boolean flag — that makes reporting a match trivial). DFS from every cell on the board; at each step, only continue into a neighboring cell if the trie has a child for that cell's letter — this is the pruning that makes searching many words at once fast. When a DFS path lands on a trie node holding a word, record it, then clear that node's word so it can't be reported twice. Mark cells visited during the DFS (e.g. swap in a sentinel character) and restore them on the way back out.

Skeleton

trie = build_trie(words)
for each cell (r, c):
    dfs(r, c, trie.root)

def dfs(r, c, node):
    ch = board[r][c]
    if ch not in node.children: return
    child = node.children[ch]
    if child.word: record(child.word); child.word = None
    mark visited, board[r][c] = '#'
    for each neighbor: dfs(neighbor, child)
    board[r][c] = ch  # backtrack

Solution

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.word: str | None = None


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

    rows, cols = len(board), len(board[0])
    found: list[str] = []

    def dfs(r: int, c: int, node: TrieNode) -> None:
        ch = board[r][c]
        child = node.children.get(ch)
        if child is None:
            return

        if child.word is not None:
            found.append(child.word)
            child.word = None  # avoid reporting the same word twice

        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  # backtrack

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

    return found

Complexity

O(rows · cols · 4^L) time in the worst case, where L is the longest word — but the trie pruning cuts this drastically in practice by killing branches with no matching prefix. O(total characters across words) space for the trie.

Pitfalls

• Running plain word-search once per target word instead of building a shared trie — correct, but throws away the whole point of batching: re-walking identical prefixes for every word independently.
• Forgetting to clear child.word after recording a match — the same word can then appear multiple times in the output if the board offers more than one path to it.
• Not backtracking the visited marker (board[r][c] = ch) before returning — leaves the board corrupted for sibling DFS calls exploring other directions from an ancestor cell.