对于Data Structures项目,我必须找到两个单词之间的最短路径(例如"cat"和"dog"),一次只能更改一个字母.我们给出了一个拼字游戏单词列表,用于查找我们的路径.例如:
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度优先搜索解决了这个问题,但我正在寻找更好的东西(我用trie代表字典).
请给我一些更有效的方法(在速度和记忆方面)的想法.有些荒谬和/或挑战是首选.
我问过我的一个朋友(他是一名大三学生),他说这个问题没有有效的解决办法.他说我会学习为什么我参加算法课程.对此有何评论？
我们必须一个接一个地移动.我们不能去cat -> dat -> dag -> dog.我们还必须打印出遍历.
我刚读了使用双向搜索(在最短路径NetworkX实现Dijkstra算法的这个).这种方法的终止点是什么？