写一种拼字算法

Question

我正在研究一个类似填字游戏的问题，但我不知道如何设计算法。

例如：

• 字典里有“汽车”、“苹果”这样的词。
• “app”这个词是在黑板上写的。
• 有一些字母像'l‘e’c‘r’.用来造词。

因此，该算法的任务是使字典中存储的单词正确。

app -> lapp -> leapp -> lecapp -> .-> lappe -> eappc -> . -> appl ->苹果(正确答案)

这个算法的最佳解决方案是什么？

Answer 1

你可能有兴趣谷歌的研究论文“世界上最快的拼字游戏计划”由阿佩尔和雅各布森(1988)。这些算法都是用伪代码描述的，所以需要做一些工作才能将其塑造成可使用的形式，并将其粘合在一起；然而，作者所勾勒的程序工作得很好。

Answer 2

将您的字典存储为树，例如：

          *
          |
     +----+----+
     |         |
     A*        B
     |         |
  +--+--+      E*
  |     |      |
  P     S    +-+-+
  |     |    |   |
  P*    K*   A   E*
  |          |
+-+-+      +-+-+
|   |      |   |
E   L      D*  N*
|   |
A   E*
|
L*

谢谢你让我的树更易读。

这棵树有单词a，应用程序，吸引力，苹果，询问，珠，豆，被，和蜜蜂。标记为星号的节点表示“如果我在这里停止，这将是一个有效的单词”，例如'b‘下面的'e’表示' be‘。

当你找到一个你不知道的字母时，使用通配符(即，挑选所有的孩子，然后沿着所有的路径返回)。

你说的是填字游戏，但是你的"letters...for造字“似乎代表了拼字游戏。这两种方法都适用。不是最快的，而是很快的。

谢谢安德烈亚斯提醒我们，这被称为trie。

如果你想说“第二个字母是一个P”，你可以从根节点开始，取每一个分支(这是字母表中的每个字母，假设它是一个恰当的字典)，然后"P“分支然后从那里继续。

Answer 3

实际上，我以前写过一个纵横字谜程序(神秘，但其背后的理论是相同的)。

我有一个单词及其线索的数据库，可以根据使用的时间进行排序(这样我就不会在以后的运行中得到重复的字谜)。

你应该做的第一件事是设计你的图案(黑人在你不能放字母的地方，白色在你可以的地方)。尝试在动态创建模式的同时将单词放入网格中是非常耗时的，而且容易出错。如果你看大多数填字游戏，他们往往会遵循一定的规则，以使它更容易。比如在对角线周围对称，不允许一个由四个白细胞组成的正方形(以方便选择合适的单词)。

一旦你有了这个模式，你就会开始在里面找到合适的词。这样，你就会知道"app“是单词的开头，并且可以将搜索限制在以"app”开头的搜索，而不是每个在其中包含"app“的单词。同样地，对于你在任何位置都认识字母的单词。在已知的位置定位字母要比在单词中的任何起始位置评估这些字母容易得多。

我的最终是用shell脚本编写的(信不信由你)，并使用来自Linux的字典作为单词搜索工具。如果你知道你有一个以"app“开头的5个字母的单词，它很容易使用：

grep '^app..$' words.txt

以获得所有有效可能性的列表。

并且，当每个单词被找到时，它被复制到一个包含单词和多个可能的线索的clues.txt文件中。实际格式是使用{count、word、lesser }，其中相同的单词可能存在于多行上，具有不同的线索--这允许grep通过sort的管道，以便较少使用的单词/线索浮到顶部(每当使用单词/线索时，其计数就会增加，因此下一次不太可能使用)。

一旦该文件具有相当的大小，该程序将首先使用它来定位单词，并且只有在找不到一个文件时，它才会恢复到需要手动干预的单词文件(无线索)。

实际上，它最终还是很擅长做这份工作。它的速度并不快得令人目眩，但我不需要每三秒生成一次--这是一份每周发送一次的社区时事通讯。

既然你已经把这个问题变成了拼字游戏的变体，那就更难了。

你需要考虑到你拥有的字母，董事会上的字母，还有你需要评估的更多的地方。这使得蛮力法更加困难。

我要做的是作为一个初步的削减将选择可能性(开始位置和方向在板上)随机选择，然后使用相同的算法，对上面的纵横字谜变体，以找到所有的词，可以适合那里。然后，如果你有满足这个单词的字母，将它(连同它的分数)存储在一个列表中。

请记住，你需要小心，以免干扰董事会上的其他词。

我将继续研究各种可能性，直到下列之一：

• 您的列表足够大，可以从中选择。
• 你没时间了。
• 你已经研究了足够多的可能性来满足你的能力水平。

最后一个是很重要的--如果你是初学者，你不想穷尽地研究无数的可能性。

然后，从你的列表中选择最好的一步(或者如果在初学者的水平上玩的话，也可能不是最好的--这完全取决于你想要的电脑有多好)。