#189HardBacktracking· Trie-Guided Grid Search

Word Hunt Grid

A word-hunt puzzle shows a grid of letters. A word is **found** if it can be spelled by walking from cell to cell, where each step moves to a cell directly above, below, left or right of the previous one, and **no cell is used twice** within one word. Given the grid and a list of candidate words, return all candidate words that can be found, in ascending alphabetical order. Each word appears at most once in the candidate list.

Input format

`grid`: an array of equal-length strings of lowercase letters; `words`: an array of distinct lowercase words.

Output format

An array of the found words in ascending alphabetical order.

Examples

Input: grid = ["oaan", "etae", "ihkr", "iflv"], words = ["oath", "pea", "eat", "rain"]

Output: ["eat", "oath"]

"oath" winds through o-a-t-h and "eat" through e-a-t. "pea" has no p and "rain" would need to reuse or jump to a non-adjacent cell.

Input: grid = ["ab", "cd"], words = ["abcd", "abdc"]

Output: ["abdc"]

a-b-d-c is a valid path around the square; a-b-c-d is not, because b and c are diagonal.

Input: grid = ["a"], words = ["a", "aa"]

Output: ["a"]

"a" is found; "aa" would need to use the single cell twice.

Constraints

1 <= grid.length, grid[i].length <= 10
1 <= words.length <= 3000
1 <= words[i].length <= 10
All strings contain only lowercase English letters, and all words are distinct.

Study first

Recursion and Divide and Conquer

#backtracking
#trie
#matrix
#depth-first-search
#strings