LeetCode 212 Word Search II - Example and Complexity Analysis

Trie contains "oath", "eat". Start DFS from 'o' at (0,0).

'o' exists in trie. Move to neighbors: 'a' at (0,1).

'a' exists under 'o'. Move to neighbors: 't' at (1,1).

't' exists under "oa". Move to neighbors: 'h' at (2,1).

'h' exists and "oath" is marked as word end. Add "oath" to result.

Continue DFS from other cells. Find "eat" starting from 'e' at (1,0) or elsewhere.

Build trie: $O(\sum |word|)$. DFS: worst case $O(m \cdot n \cdot 4^L)$ but heavily pruned by trie. Space: $O(\sum |word|)$ for trie.