# \[212]\[困难]\[DFS] 单词搜索 II

## 题目描述

[212. 单词搜索 II](https://leetcode-cn.com/problems/word-search-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-cn.com/problems/implement-trie-prefix-tree/description/)。

## 解题思路

### DFS + Trie树

[\[\[剑指Offer-12\]\[中等\]\[DFS\] 矩阵中的路径](/garnet/suan-fa/dfs/jian-zhi-offer12-ju-zhen-zhong-de-lu-jing.md)的扩展版. 搜索是否包含多个单词, 使用**前缀Trie树**减少遍历次数. DFS的思路与前面题目中的一样, 只是剪枝条件变了:

* 索引超越边界, 剪枝
* 当前前缀不在树中, 剪枝

搜索到单词就添加到结果中, 但不能停止, 因为可能是另一个单词的前缀.

```python
class Trie:
    def __init__(self):
        self.root = dict()

    def insert(self, word):
        root = self.root
        for c in word + '&':
            if c not in root:
                root[c] = dict()
            root = root[c]

    @lru_cache(None)
    def search(self, word):
        root = self.root
        for c in word:
            if c not in root:
                return False
            root = root[c]
        return True if '&' in root else False

    @lru_cache(None)
    def startwith(self, prefix):
        root = self.root
        for c in prefix:
            if c not in root:
                return False
            root = root[c]
        return True


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        n, m = len(board), len(board[0])
        trie = Trie()
        for w in words:
            trie.insert(w)

        res = set()

        def dfs(i, j, prefix):
            if not 0 <= i < n or not 0 <= j < m:
                return False
            new_prefix = prefix + board[i][j]
            if not trie.startwith(new_prefix):
                return False
            if trie.search(new_prefix):
                res.add(new_prefix)

            tmp, board[i][j] = board[i][j], '/'
            t = dfs(i + 1, j, new_prefix) or dfs(i - 1, j, new_prefix) or dfs(i, j + 1, new_prefix) or dfs(i, j - 1, new_prefix)
            board[i][j] = tmp
            return t

        for i in range(n):
            for j in range(m):
                dfs(i, j, '')
        return list(res)
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/dfs/212-dan-ci-sou-suo-ii.md?ask=<question>
```

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.