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.


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){
     } else
        List<String> newAnagrams = new ArrayList<String>();
        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();
  • 1
    $\begingroup$ Anagrams have the same sorted sequence of characters. I would use that. $\endgroup$ – adrianN Oct 19 '13 at 8:07
  • 2
    $\begingroup$ What do you mean here by O(1) ? What is the parameter ? $\endgroup$ – Tpecatte Oct 19 '13 at 11:39
  • 1
    $\begingroup$ To clarify Timot's question, there are two algorithms here: the precomputation done on the set of words, and the lookup of a string. There are also several parameters: the number and lengths of the words for the precomputation, and additionally the length of the string for the lookup. So when you discuss a complexity, you need to say which algorithm and look at all the parameters. $\endgroup$ – Gilles 'SO- stop being evil' Oct 19 '13 at 11:47
  • 2
    $\begingroup$ Using a hash is a good idea, but it isn't so simple. What happens if there's a hash collision? $\endgroup$ – Gilles 'SO- stop being evil' Oct 19 '13 at 11:47
  • $\begingroup$ @Timot Nothing special behind O(1). I should get all anagrams with single cycle .. like HashMap.get(string) .. or strings[10] ...I dont want to go for search. $\endgroup$ – Ajeet Singh Oct 20 '13 at 17:53

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.


Use a hash table (python dictionary or equivalent) in which the key is the sorted multiset of letters and the contents is all words composed of these letters.


Your Answer

