字符矩阵中查找单词-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)):
            prefix_set.add(w[:i+1])
    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
        visited.add((new_x, new_y))
        # 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)
————————

问题：给你一个字符矩阵和单词列表，输出字符矩阵能够组合成列表中的哪些词

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)):
            prefix_set.add(w[:i+1])
    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
        visited.add((new_x, new_y))
        # 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)