Word Search II

Reuse the classic Word Search DFS: for each word independently, try starting from every cell and backtrack through the four neighbors, matching one character at a time.

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

        def dfs(r, c, i, word, visited):
            if i == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return False
            if (r, c) in visited or board[r][c] != word[i]:
                return False
            visited.add((r, c))
            found = (
                dfs(r + 1, c, i + 1, word, visited)
                or dfs(r - 1, c, i + 1, word, visited)
                or dfs(r, c + 1, i + 1, word, visited)
                or dfs(r, c - 1, i + 1, word, visited)
            )
            visited.remove((r, c))
            return found

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

Each word triggers its own full board scan — O(m·n·4^L) per word, O(w · m·n·4^L) overall for w words. With up to 3·10^4 words this is the difference between passing and timing out: the board gets re-scanned from scratch for every single word, even though most of them share no useful structure with each other.

Insert every word into a trie first. Then do one DFS pass over the board: at each step, instead of comparing against a single target word, walk into the trie node matching the current board character. If the board character has no matching trie child, that whole direction is pruned immediately — a single DFS is effectively checking every word that shares the current prefix at once. When a trie node marks the end of a word, record it (and clear the marker so the same word cannot be reported twice).

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # holds the complete word once this node ends one

class Solution:
    def findWords(self, 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])
        result = []

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

            if child.word is not None:
                result.append(child.word)
                child.word = None  # avoid duplicate matches

            board[r][c] = '#'  # mark visited in place
            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

            if not child.children:
                del node.children[ch]  # prune dead branches so future DFS calls skip them

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

Building the trie for words = ["oath", "pea", "eat", "rain"] gives four branches (they all start with different letters, so nothing is shared here — sharing would only kick in for words with common prefixes):

With this trie built, the board DFS starts from every cell exactly once (not once per word). At (0,0) = 'o', the trie has an o child, so the DFS descends into it and finds oath along the path (0,0)->(0,1)->(1,1)->(2,1) (o,a,t,h). Starting from (1,3) = 'e', it finds eat along (1,3)->(1,2)->(1,1) (e,a,t). Cells are marked '#' while in the current path so the same cell is never reused within one word, then restored on backtrack so other starting points can still use them. Crucially, no cell on the board is ever 'p', so the trie’s root simply has no p child to descend into — "pea" is ruled out in O(1) per cell instead of needing its own dedicated scan, and "rain" is explored but fails once no adjacent path completes i then n. This matches the expected output ["eat", "oath"].

Complexity: the DFS still visits each board cell along up to 4^L paths of length L in the worst case, so it is O(m·n·4^L) — the same bound as a single Word Search — but that bound now covers all words at once instead of being multiplied by w. Deleting exhausted trie branches (del node.children[ch]) also means later cells stop descending into prefixes that can no longer lead anywhere, pruning the search further as words are found. Space is the trie itself, O(sum of word lengths), plus O(L) recursion depth for the DFS.