1
$\begingroup$

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();
   }
$\endgroup$
  • 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
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.