## 题目地址（212. 单词搜索 II）

https://leetcode-cn.com/problems/word-search-ii/description/

## 题目描述

```
给定一个二维网格 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（前缀树）。

```

## 思路

我们需要对矩阵中每一项都进行深度优先遍历（DFS）。 递归的终点是

1. 超出边界
2. 递归路径上组成的单词不在 words 的前缀。

比如题目示例：words = ["oath","pea","eat","rain"]，那么对于 oa，oat 满足条件，因为他们都是 oath 的前缀，但是 oaa 就不满足条件。

为了防止环的出现，我们需要记录访问过的节点。而返回结果是需要去重的。出于简单考虑，我们使用集合（set），最后返回的时候重新转化为 list。

刚才我提到了一个关键词“前缀”，我们考虑使用前缀树来优化。使得复杂度降低为$O(h)$, 其中 h 是前缀树深度，也就是最长的字符串长度。

![](https://tva1.sinaimg.cn/large/006tNbRwly1gb5dmstsxxj30mz0gqmzh.jpg)

## 关键点

- 前缀树（也叫字典树），英文名 Trie（读作 tree 或者 try）
- DFS
- hashmap 结合 dfs 记录访问过的元素的时候，注意结束之后需要将 hashmap 的值重置。（下方代码的`del seen[(i, j)]`）

## 代码

- 语言支持：Python3

Python3 Code：

关于 Trie 的代码:

```python
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.Trie = {}

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        curr = self.Trie
        for w in word:
            if w not in curr:
                curr[w] = {}
            curr = curr[w]
        curr['#'] = 1

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """

        curr = self.Trie
        for w in prefix:
            if w not in curr:
                return False
            curr = curr[w]
        return True
```

主逻辑代码：

```python
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        m = len(board)
        if m == 0:
            return []
        n = len(board[0])
        trie = Trie()
        seen = None
        res = set()
        for word in words:
            trie.insert(word)

        def dfs(s, i, j):
            if (i, j) in seen or i < 0 or i >= m or j < 0 or j >= n or not trie.startsWith(s):
                return
            s += board[i][j]
            seen[(i, j)] = True

            if s in words:
                res.add(s)
            dfs(s, i + 1, j)
            dfs(s, i - 1, j)
            dfs(s, i, j + 1)
            dfs(s, i, j - 1)

            del seen[(i, j)]

        for i in range(m):
            for j in range(n):
                seen = dict()
                dfs("", i, j)
        return list(res)
```

## 相关题目

- [0208.implement-trie-prefix-tree](./208.implement-trie-prefix-tree.md)
- [0211.add-and-search-word-data-structure-design](./211.add-and-search-word-data-structure-design.md)
- [0472.concatenated-words](./problems/472.concatenated-words.md)
- [0820.short-encoding-of-words](https://github.com/azl397985856/leetcode/blob/master/problems/820.short-encoding-of-words.md)