Given an m x n `board` of single-character strings and a list of `words`, return all words that can be formed by a path of horizontally or vertically adjacent cells, each cell used at most once per word. Return the found words sorted.
Figure
row · column
Examples
in: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
out: ["eat","oath"]
both are traceable on the board
Constraints
1 <= m, n <= 12 for tests
1 <= len(words) <= 3*10^4
lowercase letters
Hints
target: O(m*n*4^L) with trie pruning⌘↩ run · ⇧⌘↩ submit