Word Search II

This is the payoff problem for tries, and one of the most asked hard questions. On its own, a single-word grid search is backtracking. With thousands of words, searching for each one separately is hopeless. A trie turns thousands of searches into one.

The problem

You are given a grid of lowercase letters and a list of words. Return every word from the list that can be spelled on the grid. A word is spelled by a path of cells, each next cell directly above, below, left or right of the previous one. A cell can be used at most once within one word. Return each found word once, in any order.

Example. The board:

c a t so r e dd o g s

Words: cat, cats, card, dog, dogs, red, toe, code, cord, rat, star.

Answer: cat, cats, star, rat, red, dog, dogs, in any order.

• cat runs along the top row; cats continues to s.
• rat goes r (middle row) up to a, then right to t.
• star runs backwards along the top row, then down from a to r.
• red runs along the middle row: r, e, d.
• dog and dogs run along the bottom row.
• card, cord, code and toe are not on the board. For example, r has no neighbour d, so card and cord fail at the last letter.

Constraints. The board is up to 12 × 12. Up to 30,000 words, each 1 to 10 letters.

Clarifying questions

• Diagonal moves? No — only the four directions.
• Can a cell be reused within one word? No. Different words may use the same cells.
• Duplicate words in the list? Possible; return each found word once.
• Output order? Any order.

Approach 1: the simple way

Run the single-word search once per word: start a backtracking DFS from every cell, and stop when the whole word is matched.

1DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))234def word_exists(board: list[list[str]], word: str) -> bool:5    """Single-word search: DFS from every cell (the building block)."""6    rows, cols = len(board), len(board[0])78    def dfs(r: int, c: int, i: int) -> bool:9        if i == len(word):10            return True11        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:12            return False13        board[r][c] = "#"                        # used on this path14        found = any(dfs(r + dr, c + dc, i + 1) for dr, dc in DIRS)15        board[r][c] = word[i]                    # restore on the way out16        return found1718    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))192021def find_words_brute(board: list[list[str]], words: list[str]) -> list[str]:22    """Run a full board search once per word."""23    return [w for w in dict.fromkeys(words) if word_exists(board, w)]

One word of length L can explore up to 4 × 3^(L−1) paths from each start cell: four directions for the first step, then at most three, because you cannot step back onto the cell you came from. With 144 cells, L = 10 and 30,000 words, the worst case is 30,000 × 144 × 4 × 3^9 ≈ 3.4 × 10^11 steps. Real boards prune much of that, but the structure of the waste remains: cat and cats walk the same c-a-t path from every cell, twice.

The key insight

The words share prefixes, so the searches share work. Put all words in a trie, then walk the board and the trie at the same time. The DFS carries a trie node beside the current cell. Stepping onto a cell with letter x means stepping to the trie child x. If that child does not exist, no word in the whole dictionary continues this way, and the path stops after a single dictionary lookup.

One board search now serves all 30,000 words. Every live path is a prefix of at least one word, and every dead prefix is cut the moment it appears.

Approach 2: a trie walked with the board

1class WordNode:2    """Trie node that stores the whole word where it ends."""34    def __init__(self) -> None:5        self.children: dict[str, WordNode] = {}6        self.word: str | None = None             # set on the node where a word ends789def find_words(board: list[list[str]], words: list[str]) -> list[str]:10    """One board search for all words: walk the board and a trie together."""11    root = WordNode()12    for w in words:13        node = root14        for ch in w:15            node = node.children.setdefault(ch, WordNode())16        node.word = w17    rows, cols = len(board), len(board[0])18    found: list[str] = []1920    def dfs(r: int, c: int, parent: WordNode) -> None:21        ch = board[r][c]22        node = parent.children.get(ch)23        if node is None:24            return                               # no word continues this way25        if node.word is not None:26            found.append(node.word)27            node.word = None                     # report each word once28        board[r][c] = "#"29        for dr, dc in DIRS:30            nr, nc = r + dr, c + dc31            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":32                dfs(nr, nc, node)33        board[r][c] = ch34        if not node.children and node.word is None:35            del parent.children[ch]              # prune a branch that is used up3637    for r in range(rows):38        for c in range(cols):39            dfs(r, c, root)40    return found

Step by step:

1. Build the trie, storing the whole word on its end node instead of a flag. Then a match can be reported without rebuilding the word from the path.
2. dfs(r, c, parent) looks up the cell's letter among parent's children. No child means no word: return.
3. A word ends here: record it, then set node.word = None so a second path to the same word does not report it again.
4. Mark the cell with # so this path cannot reuse it, recurse into the in-bounds neighbours, then restore the letter. This mark-and-restore pair is backtracking.
5. Prune: if the node has no children left and no word, delete it from its parent. Later searches will not walk into a branch whose words are all found.

Dry run. The search from the top-left cell (0, 0), letter c:

After the other 11 start cells, the answer is cat, cats, star, rat, red, dog, dogs. Notice how short every dead path is: codo, cate and catsd each died after one dictionary lookup.

Complexity. Building the trie is O(S) for S total letters. The search is O(m × n × 4 × 3^(L−1)) in the worst case for an m × n board and longest word length L — the same bound as one single-word search, not one per word. In practice the trie cuts almost every branch within a step or two. Space is O(S) for the trie plus O(L) recursion depth.

Edge cases

• The same word reachable by two paths → reported once, because node.word is cleared on the first find.
• Duplicate words in the list → both inserts end on the same node, so the word is found once.
• A word that needs a cell twice → impossible, because # blocks the cell on the current path.
• A letter that appears nowhere on the board → every word starting with it dies at the root lookup, without any search.
• A word that is a prefix of another (cat, cats) → both found on one path; the search continues after reporting cat.

Follow-ups

• "Return the number of paths for each word." Do not clear node.word; count every time it is reached. Pruning must then be dropped as well.
• "Diagonal moves allowed." Add the four diagonal directions; the branching factor becomes 8 then 7, and the trie matters even more.
• "The board is huge and the dictionary small." The same code works; pruning keeps the search near the few cells whose letters start a word.