LeetCode 212 Word Search II - Solution

Build a Trie from all words. DFS on the grid, following Trie paths.

The trick is: Trie lets you search all words simultaneously. If current path isn't a prefix of any word, prune immediately.

Example: Words ["oath","pea"]. DFS finds 'o', checks Trie. 'o' is prefix of "oath", continue. 'p' is prefix of "pea", continue. Prune paths not in Trie.

Trie + DFS. For board $m \times n$, $k$ words of length $L$: $O(m \cdot n \cdot 4^L)$ worst case, pruning helps. $O(k \cdot L)$ trie space.