题目链接: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"]
思路:
前缀树(字典树)
先做一下前缀树的数据结构208. 实现 Trie (前缀树) | 题解链接
我们把所有单词构造成前缀树
再遍历 board
用DFS分别在前缀树上跑
有不清楚的地方, 欢迎留言~
相关题型:
代码:
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
trie = {}
for word in words:
t = trie
for w in word:
t = t.setdefault(w, {})
t["end"] = 1
#print(trie)
res = []
row = len(board)
col = len(board[0])
def dfs(i, j, trie, s):
#print(i, j, trie, s)
c = board[i][j]
if c not in trie: return
trie = trie[c]
if "end" in trie and trie["end"] == 1:
res.append(s + c)
trie["end"] = 0 # 防止重复数组加入
board[i][j] = "#"
for x, y in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
tmp_i = x + i
tmp_j = y + j
if 0 <= tmp_i < row and 0 <= tmp_j < col and board[tmp_i][tmp_j] != "#":
dfs(tmp_i, tmp_j, trie, s + c)
board[i][j] = c
for i in range(row):
for j in range(col):
dfs(i, j, trie, "")
return res