• 欢迎光临~

# 字符矩阵中查找单词-python

dfs回溯算法+剪枝

```# 字符矩阵+字典 -> 矩阵和字典中同时存在的词
dic = ["doaf", "agai", "dcan"]
dic = [['d', 'o', 'a', 'f'],
['a', 'g', 'a', 'i'],
['d', 'c', 'a', 'n']]
data = ["dog", "dad", "dgdg", "can", "again"]
DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]
def find_words(words, grid):
if not words or not grid:
return []
words_set = set(words)
prefix_set = set()        # 构建候选字符，作为剪枝使用，提高效率
result = []
for w in words_set:
for i in range(len(w)):
print(f"prefix set:{prefix_set}")
for i in range(len(grid)):  # 遍历每一个点，矩阵中的每一个点出发都是一种路径
for j in range(len(grid[0])):
dfs(grid, i, j, grid[i][j], set([(i,j)]), words_set, prefix_set, result)
return result

# 递归的定义：递归递查找满足dict中的word
def dfs(grid, x, y, word, visited, words_set, prefix_set, result):
# 先剪枝，条件不满足，递归终止
if word not in prefix_set:
return
# 条件满足，结果追加；不用终止，后面可能还有更长符合要求的word
if word in words_set:
result.append(word)
# 上下左右更新节点，进入更深递归
for delta_x, delta_y in DIRECTIONS:
new_x = x + delta_x
new_y = y + delta_y
# 不满足条件直接中断，继续寻找下一个
if not is_valid(new_x, new_y, visited, grid):
continue
# word+grid[new_x][new_y] 重新开辟内存，不能破坏原来的word数据。 word += grid[new_x][new_y] 不可取
dfs(grid, new_x, new_y, word+grid[new_x][new_y], visited, words_set, prefix_set, result)
visited.remove((new_x, new_y))

def is_valid(x, y, visited, grid):
# 已访问，不取
if (x, y) in visited:
return False
# 下标越界，不取
if not (0<=x<len(grid) and 0<=y<len(grid[0])):
return False
return True

find_words(data, dic)```