我正在为实践进行编程挑战，并且无法找到用于实现解决方案的良好数据结构/算法。
背景：
如果您可以通过添加、删除或更改单个字母将一个单词变为另一个单词，则称两个单词为“相邻”。
“单词列表”是连续单词相邻的唯一单词的有序列表。
问题：
编写一个程序，将两个单词作为输入，遍历字典并在它们之间创建一个单词列表。
例子：
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
我不太确定如何解决这个问题，我的第一次尝试涉及创建第一个单词的排列，然后尝试替换其中的字母。我的第二个想法可能是后缀树之类的东西
任何关于至少解决问题的想法或想法都会受到赞赏。请记住，这不是家庭作业，而是我自己正在解决的编程挑战。
这个谜题首先由查尔斯·道奇森提出，他以笔名刘易斯·卡罗尔写了《爱丽丝梦游仙境》。
基本思想是创建一个图结构，其中节点是字典中的单词，边连接相隔一个字母的单词，然后在图中进行广度优先搜索，从第一个单词开始，直到找到第二个字。
我在我的博客上讨论了这个问题，并给出了一个实现，其中包括一个用于识别“相邻”单词的巧妙算法。
我不知道这是否是您正在寻找的解决方案类型，但一个活跃的研究领域是构建“编辑距离 1”字典以快速查找相邻单词（使用您的说法）以获取搜索词建议、数据输入校正和生物信息学（例如发现染色体中的相似性）。参见例如这篇研究论文。如果没有为整个字典编制索引，至少这可能会建议您使用一种搜索启发式方法。
我自己做了这个并用它来创建一个（不是很好的）Windows 游戏。
我使用了其他人推荐的将其实现为图形的方法，其中每个节点都是一个单词，如果它们在一个字母上不同，它们就会连接起来。这意味着您可以使用众所周知的图论结果来查找单词之间的路径（例如简单的递归，其中知道距离 1 的单词可以让您找到距离 2 的单词）。
棘手的部分是建立图表。坏消息是它是 O(n^2)。好消息是它不必实时完成——而不是您的程序从文件中读取字典单词，而是读取您之前烘焙的数据结构。
关键的见解是顺序无关紧要，事实上它会妨碍。您需要构建另一种形式来保存去除订单信息并允许更轻松地比较单词的单词。您可以在 O(n) 中执行此操作。你有很多选择；我会展示两个。
对于我退出的单词谜题，我经常使用我称之为字谜字典的编码。一个词由另一个具有相同字母但按字母顺序排列的词表示。所以“汽车”变成了“汽车”。列表和狭缝都变成“ilsst”。这是比原始单词更好的比较结构，但存在更好的比较（但是，对于其他单词谜题，它是一个非常有用的结构）。
字母计数。一个包含 26 个值的数组，显示该字母在单词中的频率。所以对于“汽车”，它从 1,0,1,0,0 开始......因为有一个“a”和一个“c”。保存非零条目的外部列表（单词中出现哪些字母），因此您最多只需要检查 5 或 6 个值而不是 26 个。通过确保最多两个来快速比较以这种形式保存的两个单词非常简单计数不同。这是我会使用的。
所以，我就是这样做的。
我写了一个程序来实现上面的数据结构。
它有一个名为 WordNode 的类。这包含原始单词；一个字母不同的所有其他 WordNode 的列表；一个由 26 个整数组成的数组，给出每个字母的频率，字母计数数组中的非零值列表。
初始化程序填充字母频率数组和相应的非零值列表。它将连接的 WordNode 列表设置为零。
在为每个单词创建了 WordNode 类的实例后，我运行了一个比较方法，该方法检查频率计数是否在不超过两个位置不同。这通常比单词中的字母要少一些；还不错。如果它们恰好在两个地方不同，它们相差一个字母，我将该 WordNode 添加到仅一个字母不同的 WordNode 列表中。
这意味着我们现在有了一个字母不同的所有单词的图表。
您可以导出整个数据结构或去掉字母频率和其他不需要的东西并保存（我使用序列化 XML。如果你这样做，请确保检查它是否处理 WordNodes 列表作为参考和不是嵌入的对象）。
然后你的实际游戏只需要读取这个数据结构（而不是字典），它可以通过直接查找找到一个字母不同的单词，基本上是零时间。
可惜我的游戏很垃圾。
最简单的（递归）算法是我能想到的（嗯，我现在唯一能想到的）是
也许有更多时间的人可以为此添加 ruby 代码？
尝试这个
x = 'hate'
puts x = x.next until x == 'love'
如果您将它与字典查找结合使用，您将获得该字典中所有有效单词的列表。