查找列表中两个单词之间的路径是否存在

Question

我有一个问题想解决，我有一个单词列表：

word_list = ["DATA", "TATA", "PAPA", "PATA", "TOTO", "TITI", "TATI", "TUTO", "DARA", "DORA"]

如果两个单词之间存在路径，我想 return True。从一个词到另一个词的变化应该是通过替换一个字符。例如，“DATA”和“PAPA”之间的路径是：

DATA -> TATA -> PATA -> PAPA

DATA -> PATA -> PAPA

下面的代码打印了所有现有路径，我在其中使用了递归函数。如果路径存在或不存在（在 find_graph_words 函数内），如何将其更改为 return True|False？当我想使用 return.

时，递归函数有时会让我感到困惑

def count_diff(source, target):
    diff = 0
    for c1, c2 in zip(source, target):
        if c1 != c2:
            diff += 1
    return diff

def compute_distances(word_list):
    distances = {}
    for word in word_list:
        for target in word_list:
            if word in distances:
               maps = distances[word]
               maps[target] = count_diff(word, target)
               distances[word] = maps
            else:
               distances[word] = {target: count_diff(word, target)}
    return distances

def find_graph_words(source, target, distances, path):
    path += source + ' -> '
    to_visit = [item for item in word_list if (distances[source][item] == 1) and (item not in path)]
    if target in to_visit:
        path += target
        print(path)
    for node in to_visit:
        find_graph_words(node, target, distances, path)

if __name__ == '__main__':
    word_list = ["DATA", "TATA", "PAPA", "PATA", "TOTO", "TITI", "TATI", "TUTO", "DARA", "DORA"]
    distances = compute_distances(word_list)
    find_graph_words("DATA", "PAPA", distances, '')

Answer 1

在您现有的代码中，如果在较长的字符串中发现较短的字符串（如果您的图表中可能存在这种情况），item not in path 可能会给出错误的结果。最好为您的路径使用列表或集合结构。

为了仅测试路径的存在，您可以在递归命中后立即退出循环：

def connected(source, target, distances, path):
    to_visit = [item for item in word_list if distances[source][item] == 1 and item not in path]
    if target in to_visit:
        return True
    for node in to_visit:
        if connected(node, target, distances, path + [node]):
            return True
    return False

这可以简化为：

def connected(source, target, distances, path):
    to_visit = [item for item in word_list if distances[source][item] == 1 and item not in path]
    return target in to_visit or any(
        connected(node, target, distances, path + [node])
        for node in to_visit
    )

word_list = ["DATA", "TATA", "PAPA", "PATA", "TOTO", "TITI", "TATI", "TUTO", "DARA", "DORA"]
distances = compute_distances(word_list)
print(connected("DATA", "PAPA", distances, []))

可以先创建邻接表来提高判断效率to_visit，而不是距离矩阵，邻接表只会有距离为1的边

查找列表中两个单词之间的路径是否存在

Finding if a path between two words in a list exists

python

recursion

return