Due to recent events, I’ve been thinking about anagrams. In a nutshell, two words are anagrams if they contain the same letters. Consider for example, a function like the following:

boolean is_anagram(string worda, string wordb);

The most straight-forward approach to determining whether two words are anagrams is polynomial time. We simply compare each letter in the first word with each letter in the second word to see if exists, and mark it as being found. A more elegant approach involves normalizing the word with a hash table, and using its signature, instead of the word itself. For example, the word egg and ego could be represented as a 26-digit number:

egg: 00001020000000000000000000
ego: 00001010000000100000000000

A comparison can then be made in linear time. This technique is, unsurprisingly, the letter-signature method. If we have control over the structure of the dictionary itself, we have more efficient mechanisms. Consider then, the method signature:

array anagrams(string word, array dictionary)

In this case, we can canonicalize the words in the dictionary by rearranging each word so that its letters are alphabetical and then sorting the canonicalized set of words. Determining the anagrams of a set is simply a matter of a binary-search through the canonicalized dictionary.

A sample assignment can be found here, with further explanation. This is also a good interview question.