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

Question

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

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

例:

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

Answer 1

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

剧透:

输出是图中的路径,通过查找路径来解决问题.一个广度优先搜索(BFS)或Dijkstra算法优雅的解决这个问题.