Given a string, find all its permutations that are a word in dictionary

Question

This is an interview question:

Given a string, find all its permutations that are a word in dictionary.

My solution:

Put all words of the dictionary into a suffix tree and then search each permutation of the string in the tree.

The search time is O(n), where n is the size of the string. But the string may have n! permutations.

How do I improve the efficiency?

Answer 1

Your general approach isn't bad.

However, you can prevent having to search for each permutation by rearranging your word so that all it's characters are in alphabetical order, then searching on a dictionary where each word is similarly re-arranged into alphabetical order and mapped to the original word.

I realise that might be a little hard to grasp as is, so here's an example. Say your word is leap. Rearrange this to aelp.

Now in your dictionary you might have the words plea and pale. Having done as suggested, your dictionary will (among other things) contain the following mappings:

...
aelp -> pale
aelp -> plea
...

So now, to find your anagrams you need only find entries for aelp (using, for example, a suffix-tree approach as suggested), rather than for all 4! = 24 permutations of leap.

Answer 2

A quick alternative solution - all depends on the sizes of data structures in question.

If the dictionary is reasonable small and the string is reasonably long, you can go over each entry in the dictionary and figure out if they are a permutation of the string. You can be smarter - you can sort the dictionary and skip certain entries.