通过每次只更改一个字母将一个单词转换为另一个单词

鉴于相等的长度是在字典中的两个字，写方法通过一次改变仅一个信一个单词转换为另一个字。您在每个步骤中获得的新单词必须位于字典中。

例子：

Input: DAMP, LIKE 
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

2012-07-16 devsda

编辑距离？这是功课吗？ – 2012-07-16 17:45:21

这[wolfram博客文章]（http://blog.wolfram.com/2012/01/11/the-longest-word-ladder-puzzle-ever/）可以帮助你。 – Talon876 2012-07-16 17:50:41

作为问题的侧面提示：Levenshtein或任何其他编辑距离与每个中间词必须位于词典中的要求无关。编辑距离无论如何都是微不足道的，因为插入和删除是被禁止的。 – thiton 2012-07-16 17:51:07

尝试在graphs角度来思考这个问题：考虑在字典中的顶点的所有单词，然后插入只有一个字母不同，每两个顶点之间的边缘。输出是图中众所周知的对象，并且您可能已经知道解决该问题的算法。

扰流：

的输出是在图中的路径，并且该问题是通过找到一个路径来解决。 A breadth-first search（BFS）或Dijkstra's algorithm优雅地解决问题。

2012-07-16 17:48:01 thiton

这很有可能是OP不知道有关节点或图形的任何信息。什么是“边缘”？ – 2012-07-16 17:50:32

@RobertHarvey：感谢您的建议，链接到维基百科来定义基本概念。 – thiton 2012-07-16 18:06:15

主席先生，您能否详细说明如何以时间有效的方式将图表从字典中删除。 – devsda 2012-09-02 21:54:56

回答