Approach Summary
Insert all words into a Trie. DFS from each cell, following Trie edges. Mark found words to avoid duplicates. Prune dead Trie branches.
How to Recognize This Pattern
- "Find all words from a list in a grid"
- Trie prunes search: abort branch if no word shares the prefix
Complexity Analysis
Time Complexity
O(M × N × 4 × 3^(L-1))
Space Complexity
O(∑ word lengths)
Tags
Array String Backtracking Trie Matrix