The Anagram Problem

by Carl Furrow — on  ,  ,  , 

Taken from


Given a list of words L, find all the anagrams in L in the order in which they appear in L.


The word list:

[“pool”, “loco”, “cool”, “stain”, “satin”, “pretty”, “nice”, “loop”]

The output should be, in exactly this order:

[“pool”, “loco”, “cool”, “stain”, “satin”, “loop”]


I started reading the above post when I thought I should stop reading and try it myself. I too, started with a very naive approach that was looping over the list in exponential time. Gross.

As I read more, he said the interviewer suggested getting it to O(N) time by using a hash map. I stopped reading once more, and went back to my half-baked problem.

I came up with something that processes the output as it’s reading words in. It’s still rough, but it doesn’t loop back over the list of words, which is nice.

Step 1: Read in the words, remembering their place in the original string

Step 2: Create a hash of the word that will map similar words to the same hash

I figured I’d create a hash of a word that took each letter, and the count of each letter as it appeared in the word, the sort the letters and place the count next to it.

Example: The word “cool” would become “c1l1o2” since “c” and “l” only appear once, and “o” appears twice. That would also map “loco” to the same hash. Nice.

Why did I choose this hash method? It seemed right at the time and I originally thought it would save space. Upon reading more of the original blog post, Nafiul ends up creating a hash of a word by sorting the letters alphabetically, which is much faster/nicer. I’m keeping my hashing function as-is for full-disclosure.

Step 3: As each word is read in, create the hash, and store the word in the set of hashes.

As you can see, when I add the word to the hash map of words, I append it as the word, plus its original place in line. I’ll use that later when constructing the output.

Step 4: Build the output string

Does it work?

Yes, it does. It’s still a hot mess. Problems I see are:

  1. My “word:index” works, but I’m not in love with it. That value has to be stored somewhere, so alongside the word is probably fine, but, it feels messy. I could just do an .index_of lookup on the original word_list, but that’s technically a scan of the original word list, which would happen for every word I’m going to output.
  2. My hashing-function is a bit verbose/overkill when sorting the letters of a word would also work. I’m keeping the original here.

Full code

How about a refactor?

Knowing what I know now, and seeing the problems, let’s do some refactoring.

Hashing function

Let’s first simplify the function to do a letter-sort. It now becomes much shorter:

Wow, I’m embarrassed.

Wrap/Unwrap functions

Why didn’t I just use a hash, or an array?


Refactored full code

Now that the code is cleaner/leaner, here’s the full dump:

Yeesh, that looks a lot better. Live, code and learn.

 Want to get updates in your inbox? Sign up to receive the newsletter!
Carl Furrow's photo Author

Carl Furrow

Addicted to learning and looking to master the art of solving problems through writing code, while occasionally yelling at computer screens.