Algorithms 101: Group Anagrams in JavaScript

Noob v. Algorithms #18: fun with hashes

Joan Indiana Lyness
Nov 3 · 4 min read
image from wordsmith.org

A few days ago, I came across this challenge from LeetCode:

I thought it would be fairly difficult, but I was pleasantly surprised!

How can the definition of anagram help us sort?

You already know what an anagram is, but it pays to think about the details here. Words that are anagrams of each other share all the same letters.

Using the example above …

If we had a basket labeled“a” “e” “t” we could drop the words “ate”, “eat” and “tea” inside.

Similarly, if we had a basket labeled"t" "a" "n" we could drop the words "nat" and "tan" inside, etc.

That means we can solve this puzzle by reducing each string to its letters and then somehow connecting each set of letters to every string that contains that exact only those letters.

How will we connect them? With a hash!

We’ll build a hash that looks like this:

Our input looks like this:

[“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

To turn that into a hash, we’ll need to follow these steps.

1. set up an empty hash

let hash = {}

2. grab the letters from each string and make them a key in our new hash

To get the letters from “eat” for instance, we can use JavaScript’s .split() method:

If we add that key to our hash, we can have that key point to an array to hold anagrams using those letters. After evaluating “eat”, we’d have something like this:

hash = {
["e", "a", "t"]: ["eat"]
}

But then when we get to the word “tea”, we have a problem. It’s an anagram of “eat”, so we should add it to the same array. Instead, when we run split, we end up with the same letters in a different order …

So instead of this:

hash = {
["e", "a", "t"]: ["eat", "tea" ]
}

We end up with this:

hash = {
["e", "a", "t"]: ["eat"],
["t", "e", "a"]: ["tea"]}

To avoid this problem, after we split a string into its letters, we can alphabetize those letters. If we do this for both “eat” and “tea”, we end up with this:

hash = {
["a", "e", "t"]: ["eat", "tea ]
}

That’s exactly what we want!

3. Set up a loop to build our hash

Now that we know what we want our hash to look like, let’s set up a loop that will build our hash.

forEach loop that splits each string into letters, alphabetizes them, then adds them to hash as a key — assigns string to val
forEach loop that splits each string into letters, alphabetizes them, then adds them to hash as a key — assigns string to val

Let’s unpack that. On line 4, we’re using a forEach loop, which takes a callback function.

The callback function tells us to split each string, sort the letters, and save the result as the variable letters.

On line 7, we use a ternary function to check if our hash already has a key of letters.

If it does not already have a key of letters, we add the key and push the string (the one we just got the letters from) into that key’s value:

hash[letters].push(str)

If the key does exist, we don’t need to add the key. Instead, we go ahead and push the string into the key’s value.

After our loop has finished evaluating each string, our hash looks like this:

hash with keys of letters and values of anagrams using those letters
hash with keys of letters and values of anagrams using those letters

Last step: format output with Object.keys()

Now that we have our hash, we need to make it look like our desired output:

note: the order of the nested arrrays does not matter

We won’t need our keys. We just need to put our values into one array. (If we were using Ruby, we could simply run hash.values() ).

In JavaScript we can put all of our keys into an array and then map over the keys to return an array of all the values.

All together now:

You can play with the code here on repl.it:

https://repl.it/@Joan_IndianaInd/group-anagrams

And it’s always fun to play with on PythonTutor.com too (PythonTutor is a code visualization tool that uses many languages, not just Python!)

Here’s the link to the code on PythonTutor.

By the way — our Algorithm performs better than most on LeetCode:

© Joan Indiana Lyness 2019

In case you missed it: Algorithms 101 #17, Count Primes in JavaScript

Next: Algorithms 101 #19, Level Patio in JavaScript

JavaScript in Plain English

Learn the web's most important programming language.

Joan Indiana Lyness

Written by

Hire me in Washington DC! Full-stack developer, Ruby, Rails, JavaScript, i love! React. My portfolio: https://joan-indiana-lyness.com/projects

JavaScript in Plain English

Learn the web's most important programming language.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade