• m == board.length, n == board[i].length
• 1 <= m, n <= 12
• 1 <= words.length <= 3 × 10⁴
• 1 <= words[i].length <= 10
• board and words consist of lowercase English letters only
• All words in the list are distinct

Look at the constraint shape before anything else, because it tells you what kind of solution is wanted. The board holds at most 144 cells. The word list holds up to 30,000 words. Those numbers are wildly asymmetric, and that asymmetry is the problem.

Solve it the way the single-word version is solved: for each word, search the board for it. From every cell, try to trace the word letter by letter, backtracking whenever a letter fails to match.

def find_words(board, words):
    return [w for w in words if exists(board, w)]     # one full board search per word

Count it. Each board search starts from up to M × N cells and branches up to 4 ways per step for up to L steps, giving O(M × N × 4^L) per word. Multiply by W words: O(W × M × N × 4^L). With W at 30,000 that factor alone makes it hopeless.

But the multiplier is not the real insight. Consider what those 30,000 searches actually do. Suppose the list contains "cat", "car", "care" and "cart". Each one independently walks out to some cell holding c, then looks for a neighbouring a, and each rediscovers the identical partial route. Worse, if the board has no c at all, every one of those searches fails separately, each after its own scan of all 144 cells.

Name the waste: the words share prefixes, and the search treats them as unrelated. Every shared beginning is retraced once per word that has it.

Invert the loop. Rather than asking "where does this word appear?" for each word, walk the board once and ask, at each step, "does any word still want this prefix?"

For that question to be cheap, the words must be stored so that shared prefixes are shared structure — which is exactly what a trie provides. Each word becomes a route through a tree, one edge per character, so "cat", "car", "care" and "cart" share their first two nodes and branch only where they genuinely differ.

Now run one search over the board carrying two positions at once: where you are on the board, and where you are in the trie. Stepping to a neighbouring cell is legal only if that cell's letter is an edge out of the current trie node. When it is, both positions advance together.

The trie has stopped being storage and become an oracle. At every step it answers, in one lookup, the question that matters: is any word in the entire dictionary still consistent with the path so far? If not, abandon the path immediately — not for one word, but for all 30,000 simultaneously.

One refinement makes the code simpler: store the complete word on its terminal trie node rather than a boolean flag. Then when the search arrives at a word-ending node it can collect the answer directly, without having tracked the characters along the way.

def find_words(board, words):
    root = {}
    for word in words:                       # build the trie
        node = root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = word                     # '$' marks an end and stores the word

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

    def dfs(r, c, node):
        ch = board[r][c]
        nxt = node.get(ch)
        if nxt is None:
            return                           # no word wants this prefix: prune

        word = nxt.pop('$', None)            # found and removed in one step
        if word:
            found.append(word)

        board[r][c] = '#'                    # mark this cell used for THIS word
        for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                dfs(nr, nc, nxt)
        board[r][c] = ch                     # restore: other words may use this cell

        if not nxt:                          # subtree exhausted
            node.pop(ch)                     # prune it so nothing walks here again

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

The bound is O(M × N × 4^L) — one search per starting cell, branching 4 ways for at most L steps — with the number of words gone entirely from the expression. Space is proportional to the total characters across all words, for the trie.

Board:

o a a n
e t a e
i h k r
i f l v

Words: "oath", "pea", "eat", "rain".

The trie has four root branches: o, p, e and r.

Starting at (0,0), which holds 'o'. The root has an o edge, so descend; the trie is now at the prefix "o". No word ends here. Mark (0,0) as used and examine its neighbours: (0,1) holds a and (1,0) holds e. The "o" node's only child is a, so the e neighbour is rejected by a single dictionary lookup — no scanning, no per-word check.

Descend into (0,1), trie at "oa". Its neighbours are (0,0), already marked, (0,2) holding a, and (1,1) holding t. The "oa" node's only child is t, so the a neighbour fails instantly. Move to (1,1), trie at "oat". Its unmarked neighbours are (1,0) e, (1,2) a, (2,1) h. Only h is a child of "oat", so descend to (2,1), trie at "oath" — and this node carries a stored word. Collect "oath" and pop the marker so no later path can report it twice. The recursion then unwinds, restoring every cell it marked.

Starting anywhere holding 'p'. There is no p on the board, so this never arises — and note what did happen instead: the p branch of the trie was simply never entered. The naive approach would have scanned all 16 cells looking for "pea" before giving up. Here the cost of rejecting it was zero.

Starting at (1,3), which holds 'e'. The root has an e edge, so descend to "e". Neighbours are (0,3) n, (2,3) r, (1,2) a. The "e" node's only child is a, so only (1,2) survives. Descend, trie at "ea". Its unmarked neighbours include (1,1) holding t, which is a child of "ea". Descend to "eat" — a word node. Collect "eat".

"rain". The only r sits at (2,3). Its neighbours are (1,3) e, (3,3) v and (2,2) k. The "r" node's only child is a, and no neighbour holds one, so the path dies after a single step.

Result: ["oath", "eat"], in either order.

The idea worth extracting is loop inversion driven by the constraint shape. When one input is enormous and another is small, and the obvious solution loops over the large one running work proportional to the small one, try turning it inside out — traverse the small structure once, and consult a shared representation of the large one at each step.

The requirement is that the large collection be organised so the "is anything still consistent with what I have so far?" question is answerable in one operation. A trie does that for strings; a hash set of prefixes would do it more clumsily; other problems use sorted arrays or interval trees.

The second idea is the trie as a pruning oracle inside another search. It is not doing the searching — the depth-first walk over the board is. It is answering, at each step, whether continuing could possibly pay off. Any backtracking search with a large candidate set can be accelerated the same way, provided the candidates can be indexed by their prefixes.

Recognition signals: many patterns matched against one text or structure simultaneously. Multi-pattern string matching, censoring a document against a blocklist, autocomplete over a partially typed path, crossword solving. If the alternative is running one search per pattern, a trie over the patterns usually collapses the whole outer loop.

Train the reflex: when a search would be repeated once per item in a large collection, stop and ask whether the collection can be folded into a single structure the search consults as it goes. Searching for 30,000 words at once costs barely more than searching for one.