Word Search II

Intuition

Searching for each word independently repeats a lot of work when words share prefixes. A trie collapses those shared prefixes into a single structure, so one grid traversal can pursue many candidate words at once. As the DFS walks the board, it moves in lockstep with the trie: if the current letter is not a child of the current trie node, that path cannot spell any target and is abandoned immediately. When we land on a trie node that marks the end of a word, we record it. Marking cells as visited during recursion prevents reusing a cell, and clearing an end marker after collecting its word avoids duplicate results.

Algorithm walkthrough

1. 1Build a trie from all target words, storing the full word at the node that ends it.
2. 2Start a DFS from each grid cell, guided by the trie root.
3. 3At each step, check that the current letter matches a child of the current trie node; if not, prune this branch.
4. 4When a node's stored word is non-empty, add it to the results and clear the marker to prevent duplicates.
5. 5Temporarily mark the cell as visited, recurse into the four neighbors, then restore the cell so other paths can use it.

Implementation

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

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for word in words:
            node = root
            for ch in word:
                node = node.children.setdefault(ch, TrieNode())
            node.word = word

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

        def dfs(r: int, c: int, node: TrieNode) -> None:
            ch = board[r][c]
            nxt = node.children.get(ch)
            if nxt is None:
                return
            if nxt.word is not None:
                result.append(nxt.word)
                nxt.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, nxt)
            board[r][c] = ch

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