Trie
LC #212Hard
Word Search II
Trie
AmazonGoogleMetaProblem
Find all words from a dictionary that exist in a 2D board where letters must be adjacent (no reuse).
backtrackingtriedfsmatrix
Constraints
- ›1 ≤ m, n ≤ 12
- ›1 ≤ words.length ≤ 3 × 10⁴
- ›1 ≤ words[i].length ≤ 10
- ›Lowercase English letters only
Example
Input
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"]Why
"eat" found; "oath" found. "pea" and "rain" cannot be formed on the board