查找两个单词之间相邻单词的列表

Question

我正在为实践编写一个编程挑战,并且无法找到用于实现解决方案的良好数据结构/算法.

背景:

如果您可以通过添加,删除或更改单个字母将一个单词更改为另一个单词,请将两个单词称为"邻近".

"单词列表"是连续单词相邻的唯一单词的有序列表.

问题:

编写一个程序,它将两个单词作为输入并遍历字典并在它们之间创建单词列表.

例子:

hate  ? love:     hate, have, hove, love
dogs  ? wolves:   dogs, does, doles, soles, solves, wolves
man   ? woman:    man, ran, roan, roman, woman
flour ? flower:   flour, lour, dour, doer, dower, lower, flower

我不太确定如何处理这个问题,我的第一次尝试涉及创建第一个单词的排列,然后尝试替换它中的字母.我的第二个想法可能是后缀树

任何想要或至少打破问题的想法都将受到赞赏.请记住,这不是家庭作业,而是我自己编写的编程挑战.

Answer 1

这个谜题是由查尔斯·道奇森（Charles Dodgson）首先提出的，他以笔名刘易斯·卡罗尔（Lewis Carroll）撰写了《爱丽丝梦游仙境》 。

基本思想是创建一个图结构，其中节点是字典中的单词，边连接相隔一个字母的单词，然后从第一个单词开始对图进行广度优先搜索，直到找到第二个词。

我在我的博客中讨论了这个问题，并给出了一个实现，其中包括用于识别“相邻”单词的巧妙算法。