使用数千个单词编写字典算法，以找到具有O（1）复杂性的给定字符串的所有字符

Question

问题陈述：假设我们有一千个单词，我们需要以数据结构维护这些单词，以使我们应该能够找到给定字符串的所有字符。我试图以o（1）的复杂性来实现这一目标。

我正在寻找一种以上方案实现的算法。我用下面的算法实现了这个问题，但我觉得我们可以提高其复杂性。任何建议都会有所帮助。

算法：

这是使用哈希代码的技巧，我们还可以使用字符直方图。

步骤1：创建质数数组。

   int primes[] = {2, 3, 5, 7, ...};

   We are using prime number to avoid false collisions.

步骤2：创建一种方法来计算单词字符串的哈希代码。

   int getHashCode(String str){
     int hash = 31;
     for(i =0 to length of str){
        hash = hash*primes['a' - str.charAt[i]];
     }
     return hash;
   }

步骤3：现在将所有单词存储在哈希图中。

void loadDictionary(String[] words){

  for( word from words for i = 0 to length of words)   {
     int hash  = getHashCode(word);
     List<String> anagrams = dictionary.get(hash);
     if(anagrams ! = null){
         anagrams.add(word);
     } else
        List<String> newAnagrams = new ArrayList<String>();
        newAnagrams.add(word);
        dictionary.put(hash, newAnagrams);
     }
  }
}

步骤4：现在是找到Anagrams的方法：

   int findNumberOfAnagrams(String str){
      List<String> anagrams = dictionary.get(getHashCode(str));
      return anagrams.size();
   }

Answer 1

您可能会从文章中获得一些灵感 世界上最快的拼字游戏 由安德鲁·W·阿佩尔（Andrew W. Appel）和 更快的拼字移动一代算法 史蒂文·A·戈登（Steven A. Gordon）。两种算法都依赖于有限自动机的巧妙使用。

另请参阅此 问题 在stackoverflow上。

Answer 2

使用哈希表（python词典或同等表），其中关键是分类的多个字母，其中内容是由这些字母组成的所有单词。