我有一個要解決的問題，即我有一個單詞串列：
word_list = ["DATA", "TATA", "PAPA", "PATA", "TOTO", "TITI", "TATI", "TUTO", "DARA", "DORA"]
True如果兩個單詞之間存在路徑，我想回傳。從一個詞到另一個詞的變化應該是通過替換一個字符。例如，“DATA”和“PAPA”之間的路徑是：
DATA -> TATA -> PATA -> PAPA
DATA -> PATA -> PAPA
下面的代碼列印了所有現有的路徑，我使用遞回函式來做到這一點。如何將其更改return True|False為路徑是否存在（find_graph_words函式內部）？當我想使用 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, '')
uj5u.com熱心網友回復：
在您現有的代碼中，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 的邊。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/435097.html