title
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]
示例 2：
输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]
提示：
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j]是一个小写英文字母1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i]由小写英文字母组成words中的所有字符串互不相同
solution
用trie来剪枝。
我们需要对矩阵中每一项都进行深度优先遍历（DFS）。 递归的终点是
- 超出边界
- 递归路径上组成的单词不在 words 的前缀。
比如题目示例：words = [“oath”,”pea”,”eat”,”rain”]，那么对于 oa，oat 满足条件，因为他们都是 oath 的前缀，但是 oaa 就不满足条件。
为了防止环的出现，我们需要记录访问过的节点。而返回结果是需要去重的。出于简单考虑，我们使用集合（set），最后返回的时候重新转化为 list。
刚才我提到了一个关键词“前缀”，我们考虑使用前缀树来优化。使得复杂度降低为$O(h)$, 其中 h 是前缀树深度，也就是最长的字符串长度。
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = {}
wordsSet = set(words)
for word in words:
node = root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = None
visit = set()
m, n = len(board), len(board[0])
ans = set()
def dfs(i, j, cur, node):
if not (0 <= i < m and 0 <= j < n) or (i, j) in visit or board[i][j] not in node:
return False
cur += board[i][j]
node = node[board[i][j]]
if "#" in node:
ans.add(cur)
dirs = (-1, 0, 1, 0, -1)
key = (i, j)
visit.add(key)
for k in range(4):
r, c = i + dirs[k], j + dirs[k + 1]
dfs(r, c, cur, node)
visit.remove(key)
for i in range(m):
for j in range(n):
if board[i][j] in root:
dfs(i, j, "", root)
return list(ans)