单词匹配算法

Question

我的主要想法是找到一个算法（Java），它可以接收某人在JOptionPane中键入的随机字母，然后通过按下“查找单词”按钮，立即从存储在.txt文件中的字典中派生出与我的字母匹配的所有单词。

我正在努力寻找这个算法。

例如：

考虑我们在Scrabble比赛中得到以下字母：

a, o, p, t, e, z, e, w

我想找到一段Java代码或至少是一种算法，以便从英语字典.txt文件中找到那些只包含这些字母而不包含其他任何字母的单词。如果我输入“a，p，p”，我希望结果是单词“app”，而不是（apps）。

因此...总结一下，如何将这些字母与存储在.txt文件中的单词进行比较，并得到与给定字母匹配的特定单词？

- Ane

---

你目前尝试了什么？有可用的代码吗？ - Tassos Bassoukos

请展示一些代码来展示您在制作此算法方面的开发，或者至少展示您完成它的思考过程。 - Shrey

可能是使用哈希表和/或Tries的Anagram算法的重复问题。 - hatchet - done with SOverflow

这不是一个完全的字谜。记住，它也应该匹配leap。 - McLovin

@user3295442 - 这使得该问题与上面链接中的问题不是完全重复，但是解决此变体的方法相似。还需要一步，即对搜索字符串中已排序字母集的每个排列进行重复操作。由于只考虑唯一的已排序字母集，因此其数量要比所有字母排列少得多。 - hatchet - done with SOverflow

Answer 1

根据您需要的效率不同，有不同的方法来实现此目的。

一种简单但效率较低的方法是，获取字符串并遍历整个字典文件，检查每一行是否符合要求：检查输入的每个字符是否存在于字典文件行中（制作一个临时副本并从中删除字符，以便每个可用字母只能使用一次）。

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

编辑：请注意，正如Marko Topolnik所指出的那样，计算输入字符串的所有排列将是昂贵的-因此为了避免这种情况：在每个步骤中，您仅检查哪些字母仍然可用于输入字符串，并且您仅保留作为下一个Trie分支可用的字母。

- Bernd Elkemann

---

但是随着字符串长度的增加，排列计数会急剧增加。这似乎根本不是一个好的选择。对字符串中的字符进行排序，消除多余的自由度，似乎是最好的方法。 - Marko Topolnik

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

但是你仍然需要通过回溯在Trie中找到一个混乱的路径。搜索排序后的字符串显然更优，但它需要一个自定义的Trie，该Trie保存所有实际条目，这些条目按位置排序为字符串。 - Marko Topolnik

@MarkoTopolnik 是的，它会回溯，但我认为这是无法避免的。是的，排序是一个想法，但问题是，并非输入的所有字母都需要使用。 - Bernd Elkemann

实际上，您所描述的并没有回溯(backtracking)：您只是发现没有AER分支并继续前进。但如果trie包含AER分支和AEX分支，则仍然会存在回溯：那时您必须访问两个分支，而不仅仅是在每个节点上只取一个匹配的分支。 - Marko Topolnik

Answer 2

可以按照以下方式完成：

1.首先检查字典中是否存在确切的单词。如果存在，则可以将它们存储在数组或列表中，按照您想要的方式进行显示。例如：
通过在JOptionPane中键入“app”，它将显示苹果或应用程序等更多相关单词。
2.如果不正确，即与字典中的任何单词都不匹配，则应用编辑距离。

- Devavrata

---

查找确切单词如何找到以/包含这些字母的单词和/或相关单词？还是“通过输入'app'...”应该属于/在第二点之后？您想检查每个其他单词之间的编辑距离吗？那将非常昂贵，而且由于字母顺序无关紧要且无法插入字母，这将使其过于复杂化。 - Bernhard Barker

我只提供我知道的解决方案！！！ - Devavrata

我如何能够进行“检查”？你有算法吗？用Java？我的想法是当我输入“a p p l e”时，显示以下单词： app，apple，leap，而不仅仅是单词“apps”，只有当我给出额外的字母“s”时才会显示。 - Ane