Word Search II
Word Search II is a hard Tries problem from the Blind 75. The key pattern is trie-guided backtracking, and a good solution runs in O(cells · 3^L) worst case time.
Problem
Return sorted distinct dictionary words that can be traced in a board using adjacent cells without cell reuse.
Examples
Example 1
Input
{"board":[["o","a","t"],["e","t","a"]],"words":["oat","tea","eat","toe"]}Output
["oat"]Example 2
Input
{"board":[["s","t","a","r"],["e","a","r","t"],["n","e","t","s"]],"words":["star","rats","tea","sent","net"]}Output
["net","rats","star","tea"]Example 3
Input
{"board":[["a","b"],["c","d"]],"words":["abcb"]}Output
[]Approach
Load all words into a trie, then search the board from every cell, following trie edges only. A node that ends a word records it.
| Pattern | Trie-guided backtracking |
|---|---|
| Time | O(cells · 3^L) worst case |
| Space | O(total word length) |
Watch out for
Mark cells as used during a path and restore them afterwards; collect words in a set so each appears once.