Word Search II

Given a 2-D grid of characters board and a list of strings words, return all words that are present in the grid.

For a word to be present it must be possible to form the word with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Approach

Build a trie from all words, then run DFS from each board cell. As you traverse, follow trie edges and backtrack on mismatch. When you reach a trie node with a stored word, add it to the result and clear it to avoid duplicates. Mark visited cells in-place to prevent reuse.

Why It Works

The trie prunes searches that cannot lead to any word, and DFS explores all valid paths on the board. A word exists exactly when there is a path whose characters match a trie path to a word-ending node. Clearing the word after discovery ensures each word is reported once.

Complexity

• Time: O(m * n * 4^L) worst-case, with strong pruning from the trie
• Space: O(total characters in trie + L) for recursion

Reference Implementation (Python)

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:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.word = word

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

        def dfs(r: int, c: int, node: TrieNode) -> None:
            ch = board[r][c]
            if ch not in node.children:
                return
            nxt = node.children[ch]
            if nxt.word:
                result.append(nxt.word)
                nxt.word = None

            board[r][c] = '#'
            if r > 0:
                dfs(r - 1, c, nxt)
            if r + 1 < rows:
                dfs(r + 1, c, nxt)
            if c > 0:
                dfs(r, c - 1, nxt)
            if c + 1 < cols:
                dfs(r, c + 1, nxt)
            board[r][c] = ch

            if not nxt.children:
                node.children.pop(ch, None)

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

        return result