0212. 单词搜索 II · ttttt

# 0212. 单词搜索 II ## 题目地址（212. 单词搜索 II） <https://leetcode-cn.com/problems/word-search-ii/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个二维网格 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 ## 公司 - 百度 - 字节 ## 思路我们需要对矩阵中每一项都进行深度优先遍历（DFS）。递归的终点是 1. 超出边界 2. 递归路径上组成的单词不在 words 的前缀。比如题目示例：words = \["oath","pea","eat","rain"\]，那么对于 oa，oat 满足条件，因为他们都是 oath 的前缀，但是 oaa 就不满足条件。为了防止环的出现，我们需要记录访问过的节点。而返回结果是需要去重的。出于简单考虑，我们使用集合（set），最后返回的时候重新转化为 list。刚才我提到了一个关键词“前缀”，我们考虑使用前缀树来优化。使得复杂度降低为O(h)O(h)O(h), 其中 h 是前缀树深度，也就是最长的字符串长度。 ![](https://img.kancloud.cn/34/0c/340c37fc6c68e2b73809d19d20a78a96_827x602.jpg) ## 关键点 - 前缀树（也叫字典树），英文名 Trie（读作 tree 或者 try） - DFS - hashmap 结合 dfs 记录访问过的元素的时候，注意结束之后需要将 hashmap 的值重置。（下方代码的`del seen[(i, j)]`） ## 代码 - 语言支持：Python3 Python3 Code：关于 Trie 的代码: ``` <pre class="calibre18">``` 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 ``` ``` 主逻辑代码： ``` <pre class="calibre18">``` 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.html) - [0211.add-and-search-word-data-structure-design](211.add-and-search-word-data-structure-design.html) - [0472.concatenated-words](472.concatenated-words.html) - [0820.short-encoding-of-words](https://github.com/azl397985856/leetcode/blob/master/problems/820.short-encoding-of-words.md) - [1032.stream-of-characters](https://github.com/azl397985856/leetcode/blob/master/problems/1032.stream-of-characters.md)