Given an m x n board of lowercase letters and a list of words, return every word from the list that can be **formed by a path on the board**.
A word is formed by starting on any cell and stepping to **horizontally or vertically adjacent** cells, spelling the word in order. The same cell may **not** be used more than once within a single word. Each word in the answer must appear in the input list, and the answer must contain **no duplicates**. The words may be returned in **any order**.
For example, on the board
o a a n
e t a e
i h k r
i f l v
with words = ["oath", "pea", "eat", "rain"], the answer is ["oath", "eat"]: "oath" traces o(0,0) → a(0,1) → t(1,1) → h(2,1), and "eat" traces e(1,3) → a(1,2) → t(1,1). "pea" and "rain" cannot be traced on the board.
Example cases
- two of four words foundin board =words = ["oath","pea","eat","rain"]oaanetaeihkriflvout ["oath","eat"]"oath" and "eat" trace valid adjacent paths; "pea" and "rain" cannot.
- no word fitsin board =words = ["abcb"]abcdout []"abcb" would reuse the cell 'b', which isn't allowed, so nothing is found.
Constraints
- m == board.length
- n == board[i].length
- 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.
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
["oath","pea","eat","rain"]