192. Word Search II
You are given an m × n grid of lowercase letters board and a list of distinct strings words. A word can be traced through the grid by starting on any cell and repeatedly stepping to an edge-adjacent cell — up, down, left, or right, never diagonally — spelling the word one letter per cell. Within a single trace no cell may be stepped on twice, but different words are free to reuse the same cells.
Return every word in words that can be traced through the board, sorted in lexicographic order (each found word listed once).
Hunting for the words one at a time works, but re-walks the same board paths over and over; the intended solution loads all the words into a trie and discovers every match in a single sweep of the grid.
Example 1:
Input: board = ["code", "rats", "maps"], words = ["oat", "zebra", "rat", "maps"]
Output: ["maps", "oat", "rat"]
Explanation: "maps" runs straight along the bottom row, while "oat" and "rat" both bend through the shared 'a' and 't' in the middle row. There is no 'z' anywhere, so "zebra" is out. The three hits are printed in dictionary order.
Example 2:
Input: board = ["ab", "cd"], words = ["abc", "da"]
Output: []
Explanation: "abc": after a → b, the cells adjacent to 'b' hold only 'a' (already used) and 'd'. "da": 'd' touches only 'b' and 'c'. Neither word can be traced, so the output is -1.
Constraints:
- 1 ≤ m, n ≤ 12
- 1 ≤ k ≤ 100 where k is the number of words
- 1 ≤ words[i].length ≤ 10
- board and words contain only lowercase English letters; all words are distinct.
Hints:
Warm up with the single-word version: a backtracking DFS that starts at every cell, marks cells while they are on the current path, and unmarks on the way back. Running it once per word is already a correct solution.
The per-word searches waste work re-exploring identical prefixes. Insert every word into a trie and run one DFS over the board that walks the trie in lockstep with the grid — a path dies the instant its letters stop being a prefix of any word.
Store each complete word at its final trie node and blank it out the first time it is reached, so nothing is reported twice. Prune harder by deleting trie nodes that no longer lead to any unfound word — the trie shrinks as matches are found.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: board = ["code", "rats", "maps"], words = ["oat", "zebra", "rat", "maps"]
Expected output: ["maps", "oat", "rat"]