# 0212. 单词搜索 II
### 题目地址（212. 单词搜索 II）
### 题目描述
```
给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。
提示:
你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。
```
### 前置知识
* [前缀树](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/trie)
* [深度优先遍历](https://github.com/azl397985856/leetcode/blob/master/thinkings/DFS.md)
* [小岛专题](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/island)
* 剪枝
### 公司
* 百度
* 字节
### 思路
我们需要对矩阵中每一项都进行深度优先遍历（DFS）。 递归的终点是
1. 超出边界
2. 递归路径上组成的单词不在 words 的前缀。
比如题目示例：words = \["oath","pea","eat","rain"]，那么对于 oa，oat 满足条件，因为他们都是 oath 的前缀。因此对于 a，oat 来说，它们**有希望**能找到 oath，但是 oaa 就不满足条件。这是一个关键点，我们的算法就是基于这个前提进行剪枝的，如果不剪枝则无法通过所有的测试用例。
这是一个典型的二维表格 DFS，和[小岛专题](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/island)套路一样：
* 四个方向 DFS。
* 为了防止环的出现，我们需要记录访问过的节点。
* 必须的时候考虑原地修改，减少 visited 的空间开销。
而返回结果是需要去重的。出于简单考虑，我们使用集合（set），最后返回的时候重新转化为 list。
刚才我提到了一个关键词“前缀”，我们考虑使用前缀树来优化。使得复杂度降低为$O(h)$, 其中 h 是前缀树深度，也就是最长的字符串长度。
关于前缀树，可以参考我的[前缀树](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/trie) 专题。
值得注意的是如果每次 dfs 都使用 startsWith 来判断，那么会超时。我们可以将当前遍历到的 trie 节点 以参数传递到 dfs 中，这样可以进一步减少复杂度。
### 关键点
* 前缀树（也叫字典树），英文名 Trie（读作 tree 或者 try）
* DFS
* 剪枝的技巧
### 代码
* 语言支持：Python3
Python3 Code：
关于 Trie 的代码:
```python
from collections import defaultdict
class Trie:
def __init__(self):
self.children = defaultdict(Trie)
self.word = ""
def insert(self, word):
cur = self
for c in word:
cur = cur.children[c]
cur.word = word
```
主逻辑代码：
```python
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
def dfs(row, col, cur):
if row < 0 or row >= m or col < 0 or col >= n or board[row][col] == '.' or board[row][col] not in cur.children: return
c = board[row][col]
cur = cur.children[c]
if cur.word != '': ans.add(cur.word)
board[row][col] = '.'
dfs(row+1,col, cur)
dfs(row-1,col, cur)
dfs(row,col+1, cur)
dfs(row,col-1, cur)
board[row][col] = c
m, n = len(board), len(board[0])
ans = set()
trie = Trie()
words = set(words)
for word in words:
trie.insert(word)
for i in range(m):
for j in range(n):
dfs(i, j, trie)
return list(ans)
```
### 相关题目
* [0208.implement-trie-prefix-tree](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/208.implement-trie-prefix-tree)
* [0211.add-and-search-word-data-structure-design](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/211.add-and-search-word-data-structure-design)
* [0472.concatenated-words](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/472.concatenated-words)
* [0820.short-encoding-of-words](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/820.short-encoding-of-words)
* [1032.stream-of-characters](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1032.stream-of-characters)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/212.word-search-ii.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.