Trie中的最短路径

对于Data Structures项目，我必须找到两个单词之间的最短路径，比如“cat”和“dog”，但我只允许一次更改一个字母。它通过实现一个线索，而不能似乎能够实现的最短路径搜索Trie中的最短路径

猫 - >摇篮 - > COG - >狗

所有词语将是相同的长度和我我从字典文件中填充它们我们必须逐字移动，所以中间的字必须是一个有效的字

我认为这是不可能的使用tr即，但任何人都有任何知识？

2013-03-08 David Chavez

注意的是，在那种特里结构的最短过去，你通常构建从字典是：每个字是一个图的顶点，但甚至没有必要建立图，您可以用字的数组来解决它不是相似度的好标准！例如，“梨”和“熊”是非常相似的，但是需要一直沿着根的方向走下去，然后再以标准方式进行。 – us2012 2013-03-08 17:38:58

你想用一个VP-Tree和算法称为Levenshtein distance AC实现可以在这里找到，代码太长了张贴作为回答：
C VP-Tree

来源

2013-03-08 17:42:00 Woot4Moo

对于这种更好的数据结构的问题是图形。这就是所谓的词梯，你可以在这里查看它：http://en.wikipedia.org/wiki/Word_ladder。

来源

2013-03-08 17:43:31

-1

你正在寻找的是一个简单的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] 
}

来源

2013-03-08 18:37:10 aram90

Trie中的最短路径

回答

相关问题