# 单词搜索 II
给定一个 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 中的所有字符串互不相同
## template
```python
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
if not board or not board[0] or not words:
return []
self.root = {}
for word in words:
node = self.root
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node["#"] = word
res = []
for i in range(len(board)):
for j in range(len(board[0])):
tmp_state = []
self.dfs(i, j, board, tmp_state, self.root, res)
return res
def dfs(self, i, j, board, tmp_state, node, res):
if "#" in node and node["#"] not in res:
res.append(node["#"])
if [i, j] not in tmp_state and board[i][j] in node:
tmp = tmp_state + [[i, j]]
candidate = []
if i - 1 >= 0:
candidate.append([i - 1, j])
if i + 1 < len(board):
candidate.append([i + 1, j])
if j - 1 >= 0:
candidate.append([i, j - 1])
if j + 1 < len(board[0]):
candidate.append([i, j + 1])
node = node[board[i][j]]
if "#" in node and node["#"] not in res:
res.append(node["#"])
for item in candidate:
self.dfs(item[0], item[1], board, tmp, node, res)
```
## 答案
```python
```
## 选项
### A
```python
```
### B
```python
```
### C
```python
```