Monday, July 18, 2011

Programming interview tip : Finding anagrams

Find all the words in a list of words (listA) which are anagrams of a single input word (wordA).

Bad solution (the trap): 
look at all the possible permutations of wordA and find them in listA.

This is a terrible solution and has a complexity of countOfCharactersInWord(wordA)!
where ! is the factorial symbol :)

Good solution:
take all the characters in wordA and sort them. Then compare it with the each item in listA first sorting the characters of that item as well :)

In python :


This yields for my friend "omair" the following interesting (i made them bold) anagrams:
mario
arimo
moria
omari
maori
moira

I used the SCOWL wordlist for this. You can get the complete working code (including the wordlist) from here:
https://bitbucket.org/basarat/pyanagram/overview
Enjoy!