Find All Words on a Board

You are given an m x n board of lowercase letters and a list of strings words. Return all words from words that can be formed by a path on the board, where consecutive letters of the word are in horizontally or vertically neighboring cells, and the same cell may not be used more than once within a single word.

Return the found words in any order, with no duplicates even if a word could be formed in multiple ways.

Example 1

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

Output: ["eat", "oath"]
Explanation:
  "oath" is spelled by the adjacent path o(0,0) -> a(0,1) -> t(1,1) -> h(2,1).
  "eat" is spelled by the adjacent path e(1,3) -> a(1,2) -> t(1,1).
  Neither "pea" nor "rain" can be formed by any path of adjacent cells
  on this board, so they are excluded from the output.

Example 2

board = [["a","b"],["c","d"]]
words = ["abcb"]

Output: []
Explanation: "abcb" would require reusing the cell containing 'b',
which is not allowed.

Constraints

• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 10^4
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All strings in words are distinct.