前缀树中的最短路径

Question

对于一个数据结构的项目，我必须找到两个单词之间的最短路径，比如“cat”和“dog”，但我只能每次更改一个字母。我试图通过实现一颗Trie树来完成它，但好像无法实现最短路径搜索。

例如：cat -> cot -> cog -> dog

所有单词的长度都将相同，并且我将从一个字典文件中填充它们。我们必须从一个单词移动到另一个单词，因此中间的单词必须是一个有效的单词。

我认为使用Trie树不太可能实现这个功能，但有没有人有相关知识？

- David Chavez

---

请注意，通常从字典构建的 trie 中的最短路径不是相似度的良好指标！例如，“pear”和“bear”非常相似，但在标准 trie 中需要一直向上到根节点再向下。 - us2012

Answer 1

你想使用一个VP-Tree，这个算法被称为Levenshtein距离。可以在这里找到一个C语言实现，代码太长了无法作为答案发布：
C VP-Tree。

- Woot4Moo

Answer 2

这种问题更适合使用图这种数据结构。它被称为单词梯子，你可以在这里查看：http://en.wikipedia.org/wiki/Word_ladder。

- Ola M

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]
}

- artahian