Given an m x n board of characters and a list of words, return all words on the board.
Each word must be constructed from sequentially adjacent cells, where adjacent cells are horizontal or vertical neighbors, and the same cell may not be used more than once in a word.
Store shared prefixes one character at a time. Distinguish between a path that exists and a complete word that ends at that path.
Examples
Input: 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"]
Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []
Constraints
- 1 <= board.length, board[0].length <= 12
- 1 <= words.length <= 30,000
- 1 <= words[i].length <= 10
- board and words consist of lowercase English letters.