Letter Grid Harvest

hard

A word-hunt puzzle deals a board of lowercase letters. A word is harvestable if you can trace it through adjacent cells (up/down/left/right), using any cell at most once per word. The scorer gets a whole list of candidate words and must report which are on the board.

Return every word from words that can be traced, in any order (no duplicates — words contains no duplicates). Running a separate board search per word repeats enormous amounts of work when words share prefixes; the fast solution searches for all words at once.

Example 1

in board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath", "pea", "eat", "rain"]

out ["oath", "eat"]

"oath" snakes o(0,0)-a(0,1)-t(1,1)-h(2,1); "eat" runs e(1,0)-a... no — e(1,3)-a(1,2)-t(1,1). "pea" and "rain" can't be traced.

Example 2

in board = [["x"]], words = ["x", "xx"]

out ["x"]

"xx" would need the single cell twice.

Constraints

· 1 <= rows, cols <= 12
· 1 <= len(words) <= 500
· 1 <= len(words[i]) <= 10
· board and words are lowercase letters
· all words are distinct