143 lines
4.3 KiB
Markdown
143 lines
4.3 KiB
Markdown
|
## 题目地址（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 是前缀树深度，也就是最长的字符串长度。
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
## 关键点
|
|||
|
|
|
|||
|
|
- 前缀树（也叫字典树），英文名 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)
|