对于Data Structures项目,我必须找到两个单词之间的最短路径(例如"cat"和"dog"),一次只能更改一个字母.我们给出了一个拼字游戏单词列表,用于查找我们的路径.例如:
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度优先搜索解决了这个问题,但我正在寻找更好的东西(我用trie代表字典).
请给我一些更有效的方法(在速度和记忆方面)的想法.有些荒谬和/或挑战是首选.
我问过我的一个朋友(他是一名大三学生),他说这个问题没有有效的解决办法.他说我会学习为什么我参加算法课程.对此有何评论？
我们必须一个接一个地移动.我们不能去cat -> dat -> dag -> dog.我们还必须打印出遍历.
可能重复:
帮助SPOJ中的算法问题
遇到了这个面试问题.给定两个n位素数,将第一个素数转换为第二个一次改变一个数字.中间数字也需要是素数.这需要以最少的步骤完成(检查素数和更改数字被视为步骤)
例如,将1033转换为8179(1033-> 1733-> 3733 - > .......-> 8179)