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

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

我不太确定如何解决这个问题，我的第一次尝试涉及创建第一个单词的排列，然后尝试替换其中的字母。我的第二个想法可能类似于 suffix tree。

如果有任何想法或想法至少可以解决问题，我们将不胜感激。请记住，这不是家庭作业，而是我正在努力应对的编程挑战。

Answer 1

这个谜题首先由查尔斯道奇森提出，他以化名刘易斯卡罗尔撰写了爱丽丝梦游仙境。

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

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