c - 通过一次仅更改一个字母将一个单词转换为另一个单词

Question

我将如何处理这个算法问题？

给定字典中长度相等的两个单词，编写一个方法，通过一次仅更改一个字母将一个单词转换为另一个单词。你每一步得到的新词必须在字典里。

例子：

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

Answer 1

试着用图来思考这个问题：将字典中的所有单词视为顶点，并在每两个仅相差一个字母的顶点之间插入一条边。输出是图中众所周知的对象，您可能已经知道解决问题的算法。

剧透：

输出是图中的一条路径，通过寻找路径来解决问题。广度优先搜索(BFS) 或Dijkstra 算法可以优雅地解决问题。