对于数据结构项目，我必须找到两个单词之间的最短路径（例如"cat" and "dog"），一次仅更改一个字母。我们得到了一个拼字游戏单词列表，用于寻找我们的路径。例如：
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度优先搜索解决了这个问题，但正在寻找更好的东西（我用特里树表示字典）。
请给我一些关于更有效方法的想法（在速度和内存方面）。一些荒谬和/或具有挑战性的事情是首选。
我问了我的一个朋友（他是大三），他说有no有效解决这个问题。他说当我参加算法课程时我就会明白为什么。对此有何评论？
我们必须从一个词到另一个词。我们不能走cat -> dat -> dag -> dog。我们还必须打印出遍历。
新答案
鉴于最近的更新，您可以尝试使用汉明距离作为启发式的 A*。这是一个可接受的启发式，因为它不会高估距离
旧答案
您可以修改用于计算的动态程序编辑距离 http://en.wikipedia.org/wiki/Levenshtein_distance来获取操作顺序。
编辑：如果字符串的数量恒定，则问题可以在多项式时间内解决。否则，它是 NP 难的（维基百科上都有）.. 假设你的朋友正在谈论这个问题是 NP 难的。
编辑：如果你的字符串长度相等，你可以使用汉明距离 http://en.wikipedia.org/wiki/Hamming_distance.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
