目录
一、概述
二、例题
2.1 构建字典树（Leetcode 208)
解题思路：实现三个方法：建立字典树、查找单词、查找前缀
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
self.end_of_word = '#'
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end_of_word] = self.end_of_word
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.end_of_word in node
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
2.2 二维网格中的单词搜索（Leetcode 79、212）
2.2.1 只有一个单词搜(Leetcode 79)
解题思路：DFS搜索
（1）暴力解法：从board中所有首字母一致的位置出发，DFS搜索word的深度，一一和word比对，时间复杂度O(4^n)
（2）剪枝：有些枝不走到底就可以放弃了
技巧：上下左右搜索可以用预先定义好的坐标移动工具来做，看起来很漂亮
dx = [-1,1,0,0]
dy = [0,0,-1,1]
class Solution:
def exist(self, board, word: str) -> bool:
self.word = word
self.word_len = len(word)
self.ret = False
if len(board) == 0 or len(board[0]) == 0:
return False
if len(word) == 0:
return False
self.m, self.n = len(board), len(board[0])
# 建立一个memory，用于存储是否访问过
visited = [[0 for _ in range(self.n)] for _ in range(self.m)]
for i in range(self.m):
for j in range(self.n):
if board[i][j] == word[0]:
visited[i][j] = 1
self._dfs(board, visited, i, j, 0)
if self.ret == True:
return True
visited[i][j] = 0
return False
def _dfs(self, board, visited, x, y, word_idx):
# 若此位置的元素和单词的该字母不一致，直接跳出递归
if board[x][y] != self.word[word_idx]:
return
# 若已经到了单词最后一个字母，都会跳出递归
if word_idx == self.word_len-1:
if board[x][y] == self.word[word_idx]:
self.ret = True
return
else:
return
# 开始往四个方向搜索
for k in range(4):
i, j = x+dx[k], y+dy[k]
# 只有边界没问题，且未访问过的位置才能访问
if i>=0 and i<self.m and j>=0 and j<self.n and visited[i][j]==0:
# 访问前将此位置设置为访问过，并在递归调用后，将此位置访问记录清零
visited[i][j] = 1
self._dfs(board, visited, i, j, word_idx+1)
visited[i][j] = 0
2.2.2 有很多单词搜（Leetcode 212）
解题思路：DFS的耗时过高，需要用字典树（其实字典树的力量只有在word特别多的时候才体现），整体就是在2.2.1上进行少许变动
dx = [-1,1,0,0]
dy = [0,0,-1,1]
class Solution:
def findWords(self, board, words):
if len(board) == 0 or len(board[0]) == 0:
return False
if len(words) == 0:
return False
# 建立字典树
self.root = {}
self.end_of_word = '#'
for word in words:
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end_of_word] = self.end_of_word
# 开始
cur_dict = self.root
self.print_flag = 0
# 存储所有找到的单词
self.ret = []
self.m, self.n = len(board), len(board[0])
visited = [[0 for _ in range(self.n)] for _ in range(self.m)]
for i in range(self.m):
for j in range(self.n):
# 起始位置需要在字典树的第一层key中
if board[i][j] in cur_dict:
print(board[i][j])
visited[i][j] = 1
self._dfs(board, visited, i, j, '', cur_dict)
self.print_flag = 0
visited[i][j] = 0
return list(set(self.ret))
def _dfs(self, board, visited, x, y, last_word, cur_dict):
# 如果字典树遍历到底了，则跳出循环
if len(cur_dict) == 0:
return
# 如果board的该位置的元素不在字典树的该层，直接跳出递归
if board[x][y] not in cur_dict:
return
# 如果有单词结束符号，则将目前的字符串计入self.ret中，但是不能跳出递归（因为可能有多个单词前缀一致）
if self.end_of_word in cur_dict[board[x][y]]:
self.ret.append(last_word+board[x][y])
# 开始向4个方向搜索
for k in range(4):
i, j = x+dx[k], y+dy[k]
if i>=0 and i<self.m and j>=0 and j<self.n and visited[i][j]==0:
visited[i][j] = 1
self._dfs(board, visited, i, j, last_word+board[x][y], cur_dict[board[x][y]])
visited[i][j] = 0