题目
给定一个二维网格 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 组成。
提示:
- 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
- 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？
方案一（散列表+深度优先搜索）——超时
class Solution:
def findWords(self, board: [[str]], words: [str]) -> [str]:
self.board = board
if not board or not board[0] or not words:
return []
# 建立散列表 key: [(0, 0)]
corrs = {}
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] not in corrs:
corrs[board[i][j]] = []
corrs[board[i][j]].append((i, j))
self.corrs = corrs
# 查找
ret = []
for word in words:
if word[0] not in corrs:
continue
# 深度优先搜索
for start_corr in corrs[word[0]]:
if self.dfs(start_corr, word):
ret.append(word)
break
return ret
def dfs(self, start_corr, word) -> bool:
'''执行一次深度优先搜索，由于递归怕栈溢出，此处采用循环
@params
- start_corr: (i, j)
- word: string
'''
visited = set([start_corr])
curr_word_index = 0 # 当前比较到的 word 的 index
stack = [(start_corr, visited, curr_word_index)]
while stack:
corr, visited, curr_word_index = stack.pop()
curr_word_index += 1
# 已经遍历到单词尾部
if curr_word_index == len(word):
return True
for next_x, next_y in self.range(corr[0], corr[1]):
if self.board[next_x][next_y] == word[curr_word_index] and (next_x, next_y) not in visited:
visited_copy = visited.copy()
visited_copy.add((next_x, next_y))
stack.append(
((next_x, next_y), visited_copy, curr_word_index))
return False
def range(self, i, j):
i_max = len(self.board)
j_max = len(self.board[0])
if i - 1 >= 0:
yield i - 1, j
if i + 1 < i_max:
yield i + 1, j
if j - 1 >= 0:
yield i, j - 1
if j + 1 < j_max:
yield i, j + 1
- leetcode 超时
方案二（trie树+深度优先搜索）——leetcode
比如我们已经知道了 basketboard 能够在二维数组 board 中生成。那么它的所有前缀一定也能生成，比如 basket 一定能够生成。
class Solution:
def __init__(self):
self.trie = {} # "end": True 表示单词结束
self.board = [[]]
self.corrs = {}
def addToTrie(self, word):
node = self.trie
for ch in word:
if ch not in node:
node[ch] = {}
node = node[ch]
node["end"] = True
def startsWith(self, word) -> bool:
node = self.trie
for ch in word:
if ch not in node:
return False
node = node[ch]
return True
def findWords(self, board: [[str]], words: [str]) -> [str]:
self.board = board
if not board or not board[0] or not words:
return []
# 建立散列表 key: [(0, 0)]
corrs = {}
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] not in corrs:
corrs[board[i][j]] = []
corrs[board[i][j]].append((i, j))
self.corrs = corrs
# 查找
ret = []
for word in words:
# 如果在 trie 树中存在前缀，则必定可以在 board 中查询到
if self.startsWith(word):
ret.append(word)
continue
if word[0] not in corrs:
continue
# 广度优先搜索
for start_corr in corrs[word[0]]:
if self.dfs(start_corr, word):
ret.append(word)
self.addToTrie(word)
break
return ret
def dfs(self, start_corr, word) -> bool:
'''执行一次深度优先搜索，由于递归怕栈溢出，此处采用循环
@params
- start_corr: (i, j)
- word: string
'''
visited = set([start_corr])
curr_word_index = 0 # 当前比较到的 word 的 index
stack = [(start_corr, visited, curr_word_index)]
while stack:
corr, visited, curr_word_index = stack.pop()
curr_word_index += 1
# 已经遍历到单词尾部
if curr_word_index == len(word):
return True
for next_x, next_y in self.range(corr[0], corr[1]):
if self.board[next_x][next_y] == word[curr_word_index] and (next_x, next_y) not in visited:
visited_copy = visited.copy()
visited_copy.add((next_x, next_y))
stack.append(
((next_x, next_y), visited_copy, curr_word_index))
return False
def range(self, i, j):
i_max = len(self.board)
j_max = len(self.board[0])
if i - 1 >= 0:
yield i - 1, j
if i + 1 < i_max:
yield i + 1, j
if j - 1 >= 0:
yield i, j - 1
if j + 1 < j_max:
yield i, j + 1
- 超时
方案三（trie树）
解法一中的想法是，从 words 中依次选定一个单词 -> 从图中的每个位置出发，看能否找到这个单词
其实可以倒过来。从图中的每个位置出发 -> 看遍历过程中是否遇到了 words 中的某个单词
遍历过程中判断是否遇到了某个单词，可以事先把所有单词存到前缀树中。这样的话，如果当前走的路径不是前缀树的前缀，我们就可以提前结束了。如果是前缀树的中的单词，我们就将其存到结果中。
class Trie:
def __init__(self, words=[]):
self.lookup = {}
for word in words:
self.add(word)
def add(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.lookup
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['is_word'] = True
def has(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.lookup
for c in word:
if c not in node:
return False
node = node[c]
# 判断是否是单词
if 'is_word' in node:
return True
return False
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.lookup
for c in prefix:
if c not in node:
return False
node = node[c]
return True
class Solution:
def __init__(self):
self.trie = Trie() # "end": True 表示单词结束
self.board = [[]]
def findWords(self, board: [[str]], words: [str]) -> [str]:
self.board = board
if not board or not board[0] or not words:
return []
# 构建 trie 树
for word in words:
self.trie.add(word)
ret = set()
def dfs(prefix, corr, visited):
if not self.trie.startsWith(prefix): # 不存在以该前缀开头的
return set()
if self.trie.has(prefix): # 找到了目标单词
ret.add(prefix)
for next_x, next_y in self.range(corr[0], corr[1]):
visited_copy = visited.copy()
if (next_x, next_y) not in visited:
visited_copy.add((next_x, next_y))
dfs(prefix + board[next_x][next_y], (next_x, next_y), visited_copy)
for i in range(len(board)):
for j in range(len(board[0])):
dfs(board[i][j], (i, j), {(i, j)})
return list(ret)
def range(self, i, j):
i_max = len(self.board)
j_max = len(self.board[0])
if i - 1 >= 0:
yield i - 1, j
if i + 1 < i_max:
yield i + 1, j
if j - 1 >= 0:
yield i, j - 1
if j + 1 < j_max:
yield i, j + 1
方案四（leetcode大佬解答）
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
trie = {}
for word in words:
t = trie
for char in word:
if char not in t:
t[char] = {} #根节点为空
t = t[char] #指向下一个节点
t["end"] = 1
def dfs(i,j,t,s):
char = board[i][j]
if char not in t:
return
t = t[char]
if "end" in t and t["end"] == 1:
res.append(s+char)
t["end"] = 0
board[i][j] = "#" # 同一单元格的单词在同一单词不重复使用
if i + 1 < m and board[i+1][j] != "#":
dfs(i+1, j, t, s+char)
if i - 1 >= 0 and board[i-1][j] != "#":
dfs(i-1, j, t, s+char)
if j + 1 < n and board[i][j+1] != "#":
dfs(i, j+1, t, s+char)
if j-1 >= 0 and board[i][j-1] != "#":
dfs(i, j-1, t, s+char)
board[i][j] = char # 恢复那个单词
m = len(board)
n = len(board[0])
res = []
for i in range(m):
for j in range(n):
dfs(i, j, trie, "")
return res
原文
https://leetcode-cn.com/explore/learn/card/trie/168/practical-application-ii/652/
若有收获，就点个赞吧
0 人点赞
