对于数据结构项目，我必须找到两个单词(如 “cat” 和 “dog”)之间的最短路径，一次只改变一个字母.我们得到了一个拼字游戏单词列表，用于查找我们的路径。例如:
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度优先搜索解决了这个问题，但我正在寻找更好的方法(我用 trie 表示字典)。
请给我一些更有效的方法(在速度和内存方面)的想法。荒谬和/或具有挑战性的东西是首选。
我问过我的一个 friend (他是大三学生)，他说这个问题没有有效的解决方案。他说我会在我参加算法类(class)时了解原因。对此有何评论？
我们必须逐字逐句。我们不能去 cat -> dat -> dag -> dog。我们还必须打印出遍历。
最佳答案
新答案
鉴于最近的更新，您可以尝试使用汉明距离作为启发式算法的 A*。这是一种可接受的启发式方法，因为它不会高估距离
旧答案
您可以修改用于计算 Levenshtein distance 的动态程序获取操作顺序。
编辑:如果字符串的数量是常数，则问题可以在多项式时间内解决。否则，它是 NP-hard(维基百科中都有).. 假设您的 friend 正在谈论这个问题是 NP-hard。
编辑:如果你的字符串长度相等，你可以使用 Hamming distance .
关于algorithm - 将一个词转换为另一个词的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1521958/