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

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

• Anagrams have the same sorted sequence of characters. I would use that. – adrianN Oct 19 '13 at 8:07
• What do you mean here by O(1) ? What is the parameter ? – Tpecatte Oct 19 '13 at 11:39
• 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. – Gilles 'SO- stop being evil' Oct 19 '13 at 11:47
• Using a hash is a good idea, but it isn't so simple. What happens if there's a hash collision? – Gilles 'SO- stop being evil' Oct 19 '13 at 11:47
• @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. – Ajeet Singh Oct 20 '13 at 17:53