Given a grid of letters and a list of words, return every word that can be formed by a path of horizontally or vertically adjacent cells, using each cell at most once per word. The words may be returned in any order.
Before you code
Searching for each word separately repeats the grid traversal once per word. How can one traversal follow every word at once?
Hints
- Insert all words into a trie, storing the complete word at its final node.
- Start a depth-first search from every cell, moving down the trie in step with the path. Stop as soon as the trie node has no child for the next letter.
- Mark cells as visited during the path and unmark them when backtracking.
- When a node holds a word, record it and clear it to avoid duplicates. Pruning trie leaves once their words are found speeds up later searches.
Production & complexity notes
When solving Word search II on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Tries to reinforce the underlying pattern.
What it practices
Using a trie to prune a search over many words, from Tries.