Print every word that is an anagram of another word in the dictionary

An anagram is any word that rearranges the letters of another word to form itself. For example, “act” and “cat” are anagrams of each other, as well as “admirer” and “married”.

Easy Solution

Compare each word against every other word in the dictionary, checking if they are anagrams of each other by sorting by character and testing for equality. This requires O(n^2) and is a working solution.

Efficient Solution

Example dictionary: {cat, dog, sad, act, cab, mat, god }
--- Sort each word only once, saving it into a temporary copy of the dictionary
Copy dictionary and sort by character: { act, dgo, ads, act, abc, amt, dgo }

Flow 1:

Use a Hashtable with hash(eachWord) as key & count as value, if count > 1 it means there is an anagram creation of the hashtable is n*mLogm (m is the average number of letters in a word and n is the total number of words in the dictionary)

Flow 2: 

We can take it one step further and gain real savings from sorting the temporary copy as well, which only costs O(n log n). It then allows you to find anagrams in O(n) time by going down the list and checking neighbors for equality. However, you’ll have to store the index into the original dictionary of the word as well since they’ll get rearranged.

Example dictionary: {cat, dog, sad, act, cab, mat, god }
Copy dictionary along with index and sort by character:
{ (act 0), (dgo 1), (ads 2), (act 3), (abc 4), (amt 5), (dgo 6) }
Sort dictionary: { (abc 4), (act 0), (act 3), (ads 2), (amt 5), (dgo 1), (dgo 6) }
Go through and find matching neighbors, extracting their indices and printing the corresponding word in the dictionary: 0, 3, 1, 6 -> cat act dog god