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();   }
Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity
algorithms;complexity theory;time complexity;strings
You may get some inspiration from the articles The world's fastest scrabble program by Andrew W. Appel and A Faster Scrabble Move GenerationAlgorithm by Steven A. Gordon.Both algorithms rely on a clever use of finite automata.See also this question on Stackoverflow.