Given a string array， return all groups of strings that are anagrams

Question

Given a string array， return all groups of strings that are anagrams.

My solutions:

For each string word in the array, sort it O(m lg m), m is the average length of a word.

Build up a hash Table < string, list >.

Put the sorted word into the hash table as key and also generate all permutations (O(m!)) of the word, search each permutation in a dictionary (a prefix tree map) with O(m), if it is in the dictionary, put (O(1)) it into the hash table so that all permutated words are put into the list with the same key.

Totally, O(n * m * lg m * m!) time and O(n* m!) space , n is the size of the given array.

If m is very large, it is not efficient , m! .

Any better solutions ?

thanks

Answer 1

We define an alphabet, which contains every letter we may have in our wordlist. Next, we need a different prime for each of the letters in the alphabet, I recommend using the smallest you can find.

That would give us the following mapping: { a => 2, b => 3, c => 5, d => 7, etc }

Now count the letters in the word you want to represent as integer, and build your result integer as follows:

Pseudocode:

result = 1
for each letter:
....result *= power(prime[letter], count(letter,word)

some examples:

aaaa => 2^4

aabb => 2^2 * 3^2 = bbaa = baba = ...

and so on.

So you will have an integer representing each word in your dictionary and the word you want to check will be able to be converted to an integer. So if n is the size of your wordlist and k is the size of the longest word it will take O(nk) to build your new dictionary and O(k) to check a new word.

Hackthissite.com has a programming challenge which is: Given a scrambled word, look it up in a dictionary to see if any anagrams of it are in the dictionary. There is a good article on an efficient solution to the problem from which I have borrowed the answer, it also goes into detail on further optimisations.