字匹配算法

我的主要想法是找到一个算法（Java），它将某人在JoptionPane中输入的随机字母作为例子，然后通过按下“查找单词”立即进行搜索，我希望该程序能够导出所有这些与存储在.txt文件中的字典匹配的字词。字匹配算法

我正在努力寻找该算法。

例如：

考虑到，我们得到了一个拼字游戏比赛下列字母：

A，O，P，T，E，Z，E，W

我会喜欢找到一个Java代码或至少一个算法，以便从英文字典.txt文件中查找具有这些字母但没有其他字的所有单词。如果我输入“a，p，p”，我希望得到单词“app”而不是（app“s”）。因此...总结一下，我怎样才能比较存储在.txt文件中的单词的字母，从而得到与我给定字母匹配的特定单词？

2014-02-20 Ane

...你到目前为止尝试过什么？任何代码可用？ –

请显示一些代码，以显示您在开发此算法的过程中。或者至少在你的思考过程中如何实现它。 – Shrey

我觉得这可以用其他语言做得更好。 –

有不同的方法可以做到这一点，具体取决于你想要的效率。

一个简单但效率不高的方法是，接收字符串并遍历整个字典文件，检查每行是否符合要求：检查输入的每个字符是否存在于dict文件中-line（对其进行临时复制并从中删除字符，以便每个可用的字母只能使用一次）。

一个更难但有效的方法是，将字典文件预处理为Trie（前缀树）[wikipedia]。然后，您可以使用输入字符串的所有排列作为通过Trie的路线图。

编辑：记为马尔科Topolnik指出，计算输入字符串的所有排列将是昂贵的 - 所以要避免的是：在每一个步骤，你只检查其中的字母仍然可以从输入字符串和那些你只保留在Trie的下一个分支中。

2014-02-20 18:32:46

但排列计数随着字符串长度而爆炸。这似乎不是一个好的追索权。对字符串中的字符进行排序，这将消除多余的自由度，似乎是最好的方式。 –

@MarkoTopolnik你不需要计算排列：在每一步你只检查哪些字母仍然可用。 **和**对于那些你只保留那些在Trie中作为下一个分支的人。 –

但是你仍然有一个通过线索的混乱路径，回溯。搜索已排序的字符串显然是优越的，但它需要一个自定义的Trie，它保存所有在每个位置按字符串排序的实际条目。 –

这可通过以下方式进行： -

1.首先检查确切的词在字典或not.If它存在，那么你可以将它们存储在数组或列表，只要你想，并显示it.for前： -
通过在JOptionPane中键入“app”，它将显示苹果或应用以及更多相关单词。
2.如果错误表示不匹配字典中的任何单词，则应用edit distance。

2014-02-20 21:03:05 Devavrata

如何查找确切单词找到以/开头/包含这些字母和/或相关单词的单词？或者是“通过键入”应用程序“......”应该在第二点之下/之后？你想检查每个单词的编辑距离吗？这将是非常昂贵的，因为信件顺序无关紧要，你不能插入字母，这将是复杂的方式。 – Dukeling

我只给出了我知道的解决方案！ – Devavrata

我怎么能够做“检查”？你脑海中有算法吗？在java中？我的想法是，当我输入“a p p l e”给我显示文字：应用程序，苹果，飞跃，而不是单词“应用程序”，只有当我给额外的字母“s”。 – Ane

回答