字典树,是一种是一种可以快速插入和搜索字符串的数据结构,有了它可以尽快的进行剪枝。
将字典的信息全部转化到字典树上,只有出现在字典树上的路径,才应该被纳入到搜索空间里。
搜索的时候不是比较target的pos是否匹配,而是比较当前board的字符是否出现在当前trie节点的子节点中。如果遇到了isWord节点,就需要将字符串加入最终的结果集中。
212. 单词搜索 II
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
trie = {}
for word in words:
node = trie
for ch in word:
if ch not in node:
node[ch] = {}
node = node[ch]
node['finish'] = word
self.res = []
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] in trie:
self.dfs(i, j, trie, board)
return self.res
def dfs(self, i, j, node, board):
cur = board[i][j]
isLast = node[cur].pop('finish', False)
if isLast:
self.res.append(isLast)
board[i][j] = '#'
for x, y in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
newx = i + x
newy = j + y
if 0 <= newx < len(board) and 0 <= newy < len(board[0]) and board[newx][newy] in node[cur]:
self.dfs(newx, newy, node[cur], board)
board[i][j] = cur
if node[cur] == {}:
node.pop(cur)
详细参考:
class Solution:
def findWords(self, board, words):
trie = {}
for word in words:
node = trie
# 针对每个单词,构造它的字典树
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node["finish"] = word
# 由于我们在下面,会把添加完单词的trie剪枝,所以不用担心会添加到重复答案的问题
self.res = []
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] in trie:
self.dfs(i, j, trie, board)
return self.res
def dfs(self, i, j, node, board):
cur = board[i][j]
"""
1.
一个单词的最后一个字母的子节点只有{finish:word}了
假如已经遍历到一个单词的最后一个字母了, pop则返回这个单词, 并记录这个单词
假如没有遍历到一个单词的最后一个字母,pop则返回默认值False
题目潜在假设,一个单词在一个表只能被找到一次,所以我们把这个单词找到后,pop掉单词
例如 {a:{b:{finish:ab}}} -> {a:{b:{}}}, 然后在下面2处进行清理
"""
isLast = node[cur].pop("finish", False)
if isLast:
self.res.append(isLast)
# 本次dfs遍历过这个点,标记,在本次不会再被访问
board[i][j] = "#"
for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
newi = i + x
newj = j + y
# 当满足所有条件的时候,我们可以把元素加进去
if 0 <= newi <= len(board) - 1 and 0 <= newj <= len(board[0]) - 1 and board[newi][newj] in node[cur]:
self.dfs(newi, newj, node[cur], board)
# 本次dfs遍历完成,解除标记,在下个dfs会被再使用
board[i][j] = cur
"""
2. 假如存在形如这种的trie, 则把b:{}给pop掉,以减少下次查询的长度
{a:{b:{}}} -> {a:{}}
"""
if node[cur] == {}:
node.pop(cur)
原文地址:http://www.cnblogs.com/ttyangY77/p/16818348.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性