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

Posted on Updated on

Problem Statement:
Suppose we 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.

Algorithms:

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<Integer, List<String>.
   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();
   }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s