Search

Google
 

Tuesday, July 17, 2007

Anagram - Generate all possible dictionary words from a given word

A contributed question ..
Generate all possible anagrams given a word.

The solution:
Create a hash dictionary (a one time operation). Which basically is a dictionay where each word is hashed to a value. The hash function must not take into accout the order in which the alpabets occur. Eg: rat and tar hash to the same value.
Once the hash lookup dictionary is in place, take the input and generate the hash using hte same hash function. This will point to a hash bucket whcih contains the list of all possible anagrams.

Running Time: constant. (Not considering generating the hash dictionary).

The same technique can be used if the question is extended to give all possible words where repetitions are allowed. The hash function should now ignore repeated alphabets. ie: shoot and shot should generate the same hash.

No comments: