找到最长字谜的算法

Question

假设我们有一个约250,000字的字典.算法应该将12个字母作为数组或字符串,并找到与字典中最长单词匹配的变体.

当然,人们总是可以蛮力,但我想知道最优雅的方式是什么？

如果不使用任何特定于语言的函数作为主要问题的快捷方式,则也将接受使用PHP以外的语言的答案.

注意:单词存储在数据库中,但我可以将它们拉入内存以提高速度.虽然我不确定PHP的索引是否优于MySQL数据库？

Answer 1

我会在这里对字谜问题的答案进行稍微修改的版本

对于字典中的每个单词，按字母顺序对字母进行排序。所以“foobar”变成了“abfoor”。

从您的完整输入开始，按字母顺序排序。如果没有找到，则删除一个字母，然后再次搜索。对每个字母都这样做。然后删除两个字母...等等。

最坏的情况：根本没有找到“字谜”。您必须测试所有可能的输入组合，这将为您提供大约 2^n 次查找，其中 n 是输入字符的数量（在您的示例中：12）但是，算法的速度并不取决于字典的大小在运行时（当然，按字母顺序对单词进行排序），我认为这是最重要的事情。