Word Search II

You get an m × n grid of lowercase letters and a list of distinct words. Return every word that can be spelled by a path of horizontally or vertically adjacent cells, using each cell at most once per word.

Return the words in any order, each at most once.

Example 1

Input: board = [["c","a","t"],
                ["r","e","d"],
                ["o","g","s"]]
       words = ["cat", "aero", "ego",
                "dog", "red", "cart"]
Output: ["cat", "aero", "ego", "red"]

"cart" fails: r isn't next to the a.

Example 2

Input: board = [["a","b"],
                ["c","d"]]
       words = ["abcb", "abdc", "acdb", "ad"]
Output: ["abdc", "acdb"]

"abcb" would reuse b; "ad" is diagonal.

Example 3

Input: board = [["a"]], words = ["a", "aa"]
Output: ["a"]

Constraints

• 1 ≤ m, n ≤ 12
• 1 ≤ len(words) ≤ 3 · 10⁴, words distinct
• 1 ≤ word length ≤ 10