php – 找到最长字谜的算法

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

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

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

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

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

从您的完整输入开始,按字母顺序排序.如果找不到,请删除一个字母,然后再次进行搜索.每封信都这样做.然后删除两个字母……依此类推.

最糟糕的情况：根本找不到’anagram’.您将必须测试所有可能的输入组合,这将为您提供大约2 ^ n个查找,其中n是输入字符的数量(在您的示例中：12)
但是,算法的速度并不取决于运行时字典的大小(当然,按字母顺序排序单词),在我看来这是最重要的事情.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!