字典树，是一种是一种可以快速插入和搜索字符串的数据结构，有了它可以尽快的进行剪枝。
将字典的信息全部转化到字典树上，只有出现在字典树上的路径，才应该被纳入到搜索空间里。
搜索的时候不是比较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)