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

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

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

如果你有任何想法或建议，至少对分解问题会很感激。请记住，这不是作业，而是我自己正在处理的编程挑战。

- Bob Templ

---

很有趣的问题。这个建议与你的问题只有间接关系，但是可以参考Levenshtein距离（http://en.wikipedia.org/wiki/Levenshtein_distance）来寻找灵感。在你的情况下，你正在寻找通过一个图的路径，该图的节点是单词，边连接具有Levenshtein距离为1的单词。这可能不是你要找的数据结构，但它可能提供一些启示。 - Chris Schmich

@ChrisSchmich 我已经研究过这个问题了，我实现了距离函数以便稍后在项目中使用。唯一的问题是这个算法不是很高效。 - Bob Templ

同样地，如果您想查看一个具体的例子，这是一个示例实现：https://github.com/dbalatero/levenshtein-ffi - fmendez

@BobTempl 我很好奇，对于初始构建或执行查询，是否有预期的运行时间/复杂度类？ - Chris Schmich

@ChrisSchmich 我不知道有没有提到时间复杂度，问题只是要求实现。我想这种问题的解决方案性能可能并不高效，但也许我只是个悲观主义者。 - Bob Templ

你正在寻找Lewis Carroll的“doublets”游戏算法。它已经在https://dev59.com/h0vSa4cB1Zd3GeqPdlii上进行了讨论。 - borrible

Answer 1

这个难题最初是由查尔斯·道奇森（Charles Dodgson）提出的，他以路易斯·卡罗尔（Lewis Carroll）的笔名写了《爱丽丝漫游奇境记》。

基本思路是创建一个图形结构，其中节点是字典中的单词，边连接相差一个字母的单词，然后通过广度优先搜索该图，在第一个单词开始，直到找到第二个单词。

我在我的博客上讨论了这个问题，并提供了一个包括识别“相邻”单词的巧妙算法的实现。

- user448810

---

+1。但你的博客有一个微不足道的问题，导致它变得不太好：你没有介绍自己。有些人只是为了解决问题而到处找答案，但有些人发现像你这样的优秀的Lisp博客后，想要知道背后的天堂是谁。我完全找不到关于我的页面。 - Boris Stitnicky

这个解决方案只适用于长度相同的字符串，对吗？ - Bob Templ

@user448810 怎么做呢？星号似乎控制着相邻返回的内容。但是唯一存在的星号是替换常规单词的字母。HATE = *ATE, H*TE, HA*E, HAT*e。我尝试将其扩展为 HATE = *HATE, H*ATE, HA*TE, HAT*E, HATE*, *ATE, H*TE, HA*E, HAT*e，但没有取得太大的成功。我的当前工作解决方案是通过实际修改字符串来生成所有相邻的单词。星号解决方案要干净得多，所以我希望能够适应它。 - Bob Templ

@user448810，我猜第一次构建图时出现了错误，感谢您的帮助。 - Bob Templ

我想看看你完成的解决方案。也许你可以在编辑中添加它。你可能还想在我的博客上添加评论，以展示程序如何轻松地进行扩展。你还可以在ideone.com上放置一个小字典，让人们可以运行它。 - user448810

Answer 2

我不知道您是否正在寻找这种解决方案，但目前研究的一个活跃领域是构建“编辑距离为1”的词典，以便快速查找相邻单词（使用您的术语）进行搜索词建议、数据输入更正和生物信息学（例如在染色体中查找相似性）。例如，请参见这篇研究论文。如果不索引整个字典，至少这可以提供您可用的一种搜索启发式方法。

- Zim-Zam O'Pootertoot

Answer 3

我已经亲自尝试了这个方法，并用它创建了一个（不是很好的）Windows游戏。我采用了其他人推荐的方法，将其实现为一张图，其中每个节点都表示一个单词，如果它们在一个字母上有所不同，则它们相连。这意味着您可以使用众所周知的图论结果来查找单词之间的路径（例如简单的递归，其中知道距离1的单词使您能够找到距离2的单词）。麻烦的部分是构建图形。坏消息是它的时间复杂度为O(n²)。好消息是它不必在实时中完成 - 您的程序读取字典中的单词而不是从文件中读取数据结构。关键的洞见是顺序无关紧要，事实上只会妨碍。您需要构建另一种形式来保存单词，并剥离顺序信息，以便更轻松地进行比较。您有很多选择；我将展示两个。第一种是字谜中常用的编码方式，称为anagram dictionary。单词由具有相同字母但按字母顺序排列的另一个单词表示。因此，“cars”变成了“acrs”。列表和槽变成了“ilsst”。这种结构比原始单词更适合进行比较，但是存在更好的比较方式（然而，它对于其他字谜非常有用）。第二种是字母计数。由26个值组成的数组，显示该字母在单词中的频率。因此，对于“cars”，它以1,0,1,0,0 ...开头，因为有一个“a”和一个“c”。保存非零条目的外部列表（哪些字母出现在单词中），因此您只需要检查最多5或6个值，而不是26个值。使用这个形式快速比较两个单词非常简单，只需确保最多有两个计数不同即可。这是我要使用的方法。所以，这就是我做到的。我编写了一个实现上述数据结构的程序。它有一个名为WordNode的类。它包含原始单词；所有其他相差一个字母的WordNodes的List；由26个整数组成的给出每个字母频率的数组，字母计数数组中的非零值列表。初始化器填充字母频率数组和相应的非零值列表。它将连接的WordNodes列表设置为零。在我为每个单词创建WordNode类的实例之后，运行比较方法，该方法检查频率计数是否在不超过两个位置处不同。通常比字母中的字母稍微少一些。如果它们在恰好两个位置不同，则它们相差一个字母，我将该WordNode添加到仅相差一个字母的WordNodes列表中。这意味着我们现在拥有所有相差一个字母的单词的图形。

你可以导出整个数据结构，也可以剥离字母频率和其他不需要的内容并保存它（我使用序列化XML。如果你选择这种方式，请确保检查它将WordNodes列表作为引用而不是嵌入式对象处理）。

你的实际游戏只需要读取这个数据结构（而不是字典），就可以通过直接查找找到一个字母不同的单词，几乎不需要时间。

可惜我的游戏很糟糕。

- Peter Webb

Answer 4

我能想到的最简单（递归）算法是（也是我此刻能想到的唯一算法）：

• 初始化一个空黑名单
• 从字典中取出所有对于当前单词是有效步骤的单词
• 删除在黑名单中的单词
• 检查是否能找到目标单词。
  • 如果不能，对上一步中找到的所有单词重复执行该算法
  • 如果能，就找到了。通过递归返回找到的路径上的所有单词。

也许有人有更多时间可以添加这个算法的Ruby代码？

- fotanus

---

我并不是真的在寻找实现，这个我可以自己完成。只是一开始遇到了困难。谢谢，这真的很有用。 - Bob Templ

Answer 5

试试这个

x = 'hate'
puts x = x.next until x == 'love'

如果你将它与字典查找结合起来，你将得到一个列表，其中包含该字典中所有有效的单词。

- Boris Stitnicky

---

我认为你误解了问题。如果只是在一个字典中查找“hate”和“love”之间的所有单词，那么这将是微不足道的。但事实并非如此。 - Bob Templ

哦，抱歉，我太快地浏览了您的问题。 - Boris Stitnicky