Word Search II

Problem

You are given a rectangular grid of lowercase letters and a list of distinct words. A word is present in the grid if you can trace it by starting at some cell and repeatedly stepping to an up/down/left/right neighbor, using each cell at most once within that single trace. Return every word from the list that is present, in any order.

• The grid is at most about a dozen rows and columns.
• The word list can hold tens of thousands of entries, each up to about ten letters.
• Grid and words contain only a–z; the words are distinct.

Examples

• Grid [["g","c","a","r"],["p","i","t","e"],["l","e","d","s"],["y","n","o","w"]], words ["pit","tied","rest","glow"] → ["pit","tied"]. "rest" fails because the t reachable from p-i is not adjacent to any s; "glow" fails because g's only neighbors are c and p, not l.
• Grid [["m","n"],["p","q"]], words ["mnpq"] → []. Tracing m-n-p would need n and p adjacent, which they are not.
• Grid [["z"]], words ["z","zz"] → ["z"]. A single cell cannot be used twice.

Hints

1. Running Word Search I once per word repeats the same grid exploration many times. What is shared across all the words?
2. Put the words in a trie, then DFS from every cell, advancing through the trie as you move. Stop the moment the current path is not a prefix of any word.
3. When a word is found, remove it from the trie (unmark the node and prune dead branches) so later DFS calls do not re-explore paths that can only yield words already found.