7

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

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

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

4

5 回答 5

15

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

于 2010-04-13T09:30:25.593 回答
4

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

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

sort_letters(word1) == sort_letters(word2)

现在要查找给定字典单词 say 的所有字谜word1，我会在字典中找到上述测试适用的所有单词。为了优化搜索，我们可以只搜索相同长度的单词。

如果我们必须反复执行此操作，最好进行一些预处理。我们可以构建类似于HashMapwhere 的东西，我们将 a 映射string到一组strings字谜。就像是：

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

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

于 2010-04-13T09:30:07.030 回答
0

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

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

于 2010-04-13T09:43:48.767 回答
0

正如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 很生锈，但我认为这样就可以了。

于 2010-04-13T09:47:47.047 回答
0

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

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

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

在 unix 系统上，您可以从words 文件开始

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

使用 precalculated 将字典转换为哈希表hashFunc。

于 2010-04-13T09:54:44.150 回答