题目描述
给出一个由小写字母组成的矩阵和一个字典。找出所有同时在字典和矩阵中出现的单词。一个单词可以从矩阵中的任意位置开始，可以向左/右/上/下四个相邻方向移动。一个字母在一个单词中只能被使用一次。且字典中不存在重复单词。
测试样例
输入：["doaf","agai","dcan"]，["dog","dad","dgdg","can","again"]
输出：["again","can","dad","dog"]
解释：
d o a f
a g a i
d c a n
矩阵中查找，返回 ["again","can","dad","dog"]。
输入：["a"]，["b"]
输出：[]
解释：
a
矩阵中查找，返回 []。
解题思路
刚开始读完题目和看完测试样例时一脸懵逼..其实题目意思是，从矩阵中任何一个位置出发，可以上、下、左、右移动，判断移动过程中组成的单词是否在字典中。另外，题目描述中“一个字母在一个单词中只能被使用一次”的实际意思是，矩阵中一个位置的字母在同一个单词中只能被使用一次，这里容易误解为一个单词中不存在重复的字母。
1、DFS
i). 先进行预处理，记录字典中所有单词的前缀（包括单词本身）集合 prefix_set，这个集合可用于判断搜索路径的有效性；
ii). 从矩阵的每个位置出发进行递归搜索，标记该位置为已使用，待搜索完毕后再取消标记；
iii). 在递归搜索过程中，先判断当前路径组成的单词是否在前缀集合中，若不在，则结束搜索；
iv). 在递归搜索过程中，判断当前路径组成的单词是否在字典中，若是，则代表已经搜索到一个单词，将其加入结果，但是并不终止搜索，这点需要注意！
v). 分别向上、下、左、右四个方向移动，注意先判断移动后的位置是否在矩阵范围内，以及该位置是否已被使用；
vi). 移动后得到矩阵对应位置的字母，继续递归搜索，同时标记该位置为已使用，待搜索完再取消标记
2、Trie
Trie是一种树形结构，是哈希树的变种。典型应用是统计、排序和保存大量的字符串（但不仅限于字符串），因此经常被搜索引擎系统用于文本词频统计。
i). 构建Trie节点数据结构TrieNode，有两个成员属性：children: dict 和 word: str，children的key是字典中单词的字母，value是TrieNode对象；word仅当在叶子节点中才会被设置（初始化为None），设置为字典中的单词，叶子节点的children的key对应该词的最后一个字母；
ii). 构建Trie数据结构，有一个成员属性root: TrieNode，以及一个insert()方法，参数是字典中的单词，这样就可以将单词的每个字母设置到各个children的key，充当了方法1中prefix_set的作用；
iii). 从矩阵中的每个位置出发进行递归搜索，标记该位置为已使用，待搜索结束后取消。在搜索过程中，若当前节点的word成员属性被设置并且未被加入到结果中，则加入到结果列表result中；
iv). 分别向上、下、左、右移动，和方法1类似，先判断移动后位置的有效性、是否被使用，这里还需要判断移动后对应位置的字母是否在当前节点的children中，如果不在，说明沿这个方向搜索下去得到的单词不会在字典中；
v). 若移动后获得一个有效位置，则标记该位置为已使用并进一步递归搜索，待搜索完毕后取消标记
代码
1、DFS
class Solution:
"""
@param board: A list of lists of character
@param words: A list of string
@return: A list of string
"""
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
def wordSearchII(self, board, words):
if not board or not words:
return []
# 记录当前位置的字符是否被使用
used = {}
result = set()
# 字典中每个单词的前缀集合
# 通过这个集合可判断每条搜索路径是否可能成功
prefix_set = set()
for word in words:
for i in range(1, len(word) + 1):
prefix = word[:i]
prefix_set.add(prefix)
for row in range(len(board)):
for col in range(len(board[0])):
pos = (row, col)
used[pos] = True
self._search(pos, board[row][col], board, words, prefix_set, used, result)
del used[pos]
# 最后需转换成list，不然会报错
return list(result)
def _search(self, pos, word, board, words, prefix_set, used, result):
# 若当前搜索到的字符组合不在前缀集合中，
# 则终止搜索
if word not in prefix_set:
return
# 若当前搜索到的字符组合在字典中，
# 则说明已形成字典中的单词，加入结果
# 注意，这里并不终止搜索！
if word in words:
result.add(word)
row, col = pos
for delta_y, delta_x in self.directions:
row_new = row + delta_y
col_new = col + delta_x
pos_new = (row_new, col_new)
# 判断移动到的位置是否在矩阵范围内
if not self._is_valid(pos_new, board):
continue
# 判断移动到的位置对应的字符是否已使用
# （一个字母在同一单词中仅允许出现一次）
if pos_new in used:
continue
used[pos_new] = True
self._search(pos_new, word + board[row_new][col_new], board, words, prefix_set, used, result)
del used[pos_new]
def _is_valid(self, pos, board):
row, col = pos
return 0 <= row < len(board) and 0 <= col < len(board[0])
2、Trie
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
class Solution:
"""
@param board: A list of lists of character
@param words: A list of string
@return: A list of string
"""
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
def wordSearchII(self, board, words):
if not board or not words:
return []
result = []
trie = Trie()
# 构建单词树，在叶子节点中设置对应的word
for word in words:
trie.insert(word)
root = trie.root
for row in range(len(board)):
for col in range(len(board[0])):
if board[row][col] in root.children:
pos = (row, col)
self._search(board, root.children[board[row][col]], pos, {pos: True}, result)
return result
def _search(self, board, node, pos, used, result):
if node.word and node.word not in result:
result.append(node.word)
row, col = pos
for delta_y, delta_x in self.directions:
row_new = row + delta_y
col_new = col + delta_x
pos_new = (row_new, col_new)
# 判断移动到的位置是否在矩阵范围内
if not self._is_valid(pos_new, board):
continue
# 判断移动到的位置对应的字符是否已使用
# （一个字母在同一单词中仅允许出现一次）
if pos_new in used:
continue
# 下一个字母必须在当前节点的孩子中
if board[row_new][col_new] not in node.children:
continue
used[pos_new] = True
self._search(board, node.children[board[row_new][col_new]], pos_new, used, result)
del used[pos_new]
def _is_valid(self, pos, board):
row, col = pos
return 0 <= row < len(board) and 0 <= col < len(board[0])
网友评论