對於Data Structures項目,我必須找到兩個單詞之間的最短路徑,比如「cat」和「dog」,但我只允許一次更改一個字母。它通過實現一個線索,而不能似乎能夠實現的最短路徑搜索Trie中的最短路徑
貓 - >搖籃 - > COG - >狗
所有詞語將是相同的長度和我我從字典文件中填充它們 我們必須逐字移動,所以中間的字必須是一個有效的字
我認爲這是不可能的使用tr即,但任何人都有任何知識?
對於Data Structures項目,我必須找到兩個單詞之間的最短路徑,比如「cat」和「dog」,但我只允許一次更改一個字母。它通過實現一個線索,而不能似乎能夠實現的最短路徑搜索Trie中的最短路徑
貓 - >搖籃 - > COG - >狗
所有詞語將是相同的長度和我我從字典文件中填充它們 我們必須逐字移動,所以中間的字必須是一個有效的字
我認爲這是不可能的使用tr即,但任何人都有任何知識?
你想用一個VP-Tree和算法稱爲Levenshtein distance AC實現可以在這裏找到,代碼太長了張貼作爲回答:
C VP-Tree
對於這種更好的數據結構的問題是圖形。 這就是所謂的詞梯,你可以在這裏查看它:http://en.wikipedia.org/wiki/Word_ladder。
你正在尋找的是一個簡單的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]
}
注意的是,在那種特里結構的最短過去,你通常構建從字典是:每個字是一個圖的頂點,但甚至沒有必要建立圖,您可以用字的數組來解決它不是相似度的好標準!例如,「梨」和「熊」是非常相似的,但是需要一直沿着根的方向走下去,然後再以標準方式進行。 – us2012 2013-03-08 17:38:58