1. 题目来源
- 分类：字典树
- Leetcode212:单词搜索II
2. 题目描述
给定一个二维网格 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 组成。
3. 解题思路
根据Trie Tree(字典树/前缀树/单词查找树)对Trie基本结构的描述，编写构建结点，以及构建trie树，以及trie树的基本操作方法。
初始化trie树，并以根结点开始对words数组中的单词进行字典树的创建，完成结果如下：
构建字典树
遍历二维网格boards进行深度搜索，对字典树路径进行匹配。当board[i][j]与node.next[x]不匹配时，node.next[ord(board[i][j]) - ord('a')] == None, 直接返回，若匹配，则把当前board[i][j]标记为已经过，之后进行深度优先遍历，并把board[i][j]加入经过路径path，当node.isEnd == True时，此路径匹配结束，并把此路径加入最后结果集中，并把当前结点node.isEnd置为False。
4. 编程实现
Python
class TrieNode:
def __init__(self):
self.isEnd = False
self.next = [None for i in range(26)]
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, words):
node = self.root
for i in range(len(words)):
if node.next[ord(words[i]) - ord('a')] == None:
node.next[ord(words[i]) - ord('a')] = TrieNode()
node = node.next[ord(words[i]) - ord('a')]
node.isEnd = True
def search(self, words):
node = self.root
for i in range(len(words)):
if node.next[ord(words[i]) - ord('a')] == None:
return False
node = node.next[ord(words[i]) - ord('a')]
return node.isEnd
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
trie = Trie()
res = []
node = trie.root
# 构建字典树
for word in words:
trie.insert(word)
# 深度搜索boards进行路径匹配
for i in range(len(board)):
for j in range(len(board[0])):
self.dfs(board, node, i, j, "", res)
return res
def dfs(self, board, node, i, j, path, res):
#结点路径匹配完毕，把存在路径加入结果集中
if node.isEnd:
res.append(path)
#对已经匹配完成的路径，避免二次匹配
node.isEnd = False
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] == '#':
return
temp = board[i][j]
node = node.next[ord(temp) - ord('a')]
if not node:
return
board[i][j] = '#'
self.dfs(board, node, i + 1, j, path + temp, res)
self.dfs(board, node, i - 1, j, path + temp, res)
self.dfs(board, node, i, j + 1, path + temp, res)
self.dfs(board, node, i, j - 1, path + temp, res)
# 便于回溯
board[i][j] = temp
