查找字典单词的anagaram

Question

如何获取输入单词（或字母序列）并从字典中输出恰好包含这些字母的单词？

java 是否有我可以使用的英语词典类（单词列表），或者是否有开源实现？

如果需要重复执行此操作，如何优化我的代码？

Answer 1

将您的字典转换为字谜字典。在字谜词典中，单词按字母顺序按字母顺序索引。要查找某个单词的字谜词，您需要对其字母进行排序，然后从字谜词典中查找相应的字母。

Answer 2

如果两个单词具有完全相同的字母、完全相同的次数，则称它们为字谜词。

字谜检查是对两个单词的字母进行排序并检查是否相等：

sort_letters(word1) == sort_letters(word2)

现在要查找给定字典单词 word1 的所有字谜，我会在字典中找到满足以下条件的所有单词：上述测试成立。为了优化搜索，我们可以只搜索相同长度的单词。

如果我们必须重复执行此操作，最好进行一些预处理。我们可以构建类似 HashMap 的东西，其中我们可以将 string 映射到一组 string（即字谜词）。就像这样：

Bad ==> Dab
Cat ==> Act, Tac
.....

现在给定任何单词，我都可以查看 hashMap 来获取它的所有字谜。

Answer 3

您可以使用 Sun 网站上的 Anagrams2 示例 作为起点

为了提高性能，您可以缓存经常使用/最近使用的单词的字谜词。考虑使用 Wea​​kHashMap 来实现此目的

Answer 4

正如 unicornaddict 提到的，您可以相当轻松地确定两个单词是否是字谜词通过排序，然而这是低效的，特别是如果你重复这样做的话。

准备好的哈希表可能是最好的解决方案，在程序开始时将字典加载到其中。一个相当容易编写的散列/比较算法将是

uint HashSomeWord(string someWord)
{
   uint hashVal = 0;
   //foreach letter in someword
   {
      //hashVal += letter.ValueAsInteger
   }
   return hashVal;
}

“

bool IsAnagram(string inputWord, string compareTo)
{
    if(inputWord == null
       || compareTo == null
       || inputWord.Length != compareTo.Length
       || HashSomeWord(inputWord) != HashSomeSome(compareTo))
    {
       return false;
    }
    if(sort_letters(inputWord) == sort_letters(compareTo))
    {
        return true;
    }
}

我的 Java 相当生锈”，但我认为这样就可以了。

Answer 5

从我的 POV 来看，此作业的关键是找到一个将字符串映射到数字的函数 (hashFunc)，以便 1) 两个字谜词映射到同一个数字，2) 映射两个非字谜词到不同的数字。一旦找到该函数，就可以简单地将其应用于输入，从而避免繁琐的字符串比较：

   if(hashFunc(word1) == hashFunc(word2)) -> word2 is anagram of word1     

java 是否有一个我可以使用的英语词典类（单词列表），或者是否有该类的开源实现？

在 Unix 系统上，您可以从 单词文件 开始

如果需要重复执行此操作，如何优化我的代码？

使用预先计算的 hashFunc 将字典转换为哈希表。