Trie中的最短路徑

Question

對於Data Structures項目，我必須找到兩個單詞之間的最短路徑，比如「cat」和「dog」，但我只允許一次更改一個字母。它通過實現一個線索，而不能似乎能夠實現的最短路徑搜索

貓 - >搖籃 - > COG - >狗

所有詞語將是相同的長度和我我從字典文件中填充它們 我們必須逐字移動，所以中間的字必須是一個有效的字

我認爲這是不可能的使用tr即，但任何人都有任何知識？

Answer 1

你想用一個VP-Tree和算法稱爲Levenshtein distance AC實現可以在這裏找到，代碼太長了張貼作爲回答：
C VP-Tree

Answer 2

對於這種更好的數據結構的問題是圖形。 這就是所謂的詞梯，你可以在這裏查看它：http://en.wikipedia.org/wiki/Word_ladder。

Answer 3

你正在尋找的是一個簡單的BFS。

words = {"cat", "dog", "dot", "cot"} 
mark = {0, 0, 0, 0} 
distance = {0, 0, 0, 0} 
queue Q 
start_word_index = 0; // words[0] -> "cat" 
destination_word_index = 1; // words[1] -> "dog" 
Q.push(start_word_index) 
while(Q is not empty) { 
    word_index = Q.pop() 
    for each `words[j]` { 
     if (difference between `words[word_index]` and `words[j]` is only 1 character) AND 
      (`mark[j]` is not 1) { 
      mark[j] = 1 
      Q.push(j) 
      distance[j] = distance[word_index] + 1 
     } 
    } 
} 

if mark[destination_word_index] is 0 { 
    print "Not reachable" 
} else { 
    print "Distance is ", distance[destination_word_index] 
}