Problem - Word Search II

Given an $m \times n$ board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (horizontally or vertically).

Example:

board = [["o","a","a","n"],
         ["e","t","a","e"],
         ["i","h","k","r"],
         ["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

The naive approach: for each word, run DFS on the board. The naive approach is slow for many words.

Better: build a trie of all words, then run one DFS from each cell, following trie paths.

Constraints: board up to $12 \times 12$, up to $3 \cdot 10^4$ words.