Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity

Problem Detail: 

Problem Statement: Suppose we have a thousands of words and we need to maintain these words in a data structure in such a way that we should be able to find all anagrams for a given string. I tried to achieve this with O(1) complexity.

I am looking for a algorithm to implement above scenario. I implemented this problem with below algo, but I feel that we can improve its complexity. Any suggestion will be helpful.

Algorithm:

Here is trick to utilise hash code, we can also use character histogram.

Step 1:Create an array of prime numbers.

   int primes[] = {2, 3, 5, 7, ...};     We are using prime number to avoid false collisions. 

Step 2:Create a method to calculate hash code of a word\string.

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

Step 3: Now store all words in a HashMap.

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);      }   } } 

Step 4: Now here is the approach to find anagrams:

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

Asked By : Ajeet Singh

Answered By : J.-E. Pin

You may get some inspiration from the articles The world's fastest scrabble program by Andrew W. Appel and A Faster Scrabble Move Generation Algorithm by Steven A. Gordon. Both algorithms rely on a clever use of finite automata.

See also this question on Stackoverflow.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16221