Group Anagrams in Javascript
--
Given an array of strings, return a new array containing all the strings with any anagrams collected together.
When I saw this challenge, I thought it might be a good application for one of my favorite problem-solving data structures: the lowly hash table.
In JavaScript, hash tables can be used through objects (not this type of JavaScript Objects) where key-value pairs, or properties, are enclosed by curly braces (i.e. {these guys}) and can be accessed via each other.
For example:
“color”: “green” would be a property, or key-value pair. This makes the stored data accessible in a new way. If I wanted to look up “green”, for example, I wouldn’t need to iterate through, searching for a match for “green. I could go straight to apple.color or apple[“color”], and find the string I wanted.
If we put the object we just made into the console, we can pull out bits of stored data quite efficiently using this approach.
Whenever a challenge requires organizing and/or comparing arrays of strings, I like using objects in this way. It saves a lot of nested iterative loops & computing time that would otherwise be used to compare & sort all those strings!
So, let’s get to it:
Our collectAnagrams function will take in an array of words. Of those words, our goal is to collect together any anagrams, then return a new array that contains all the same words, now collected into subarrays containing any anagrams.
I’ve pseudocoded out the basic steps we’ll take, and created an empty object and an empty array that we’ll use to organize, collect, and ultimately return our anagrams.
First, we’ll need to iterate through our array of words — I’m using a for/of loop to iterate over the array values.
First, we want to make the key of our key-value pair.
For each word, I want an alphabetized string of all the letters which I can compare against other possible anagrams. Object keys need to be strings, so I’m going to split the string into an array, sort it (which will alphabetize an array of characters, as letters found earlier in the alphabet register as smaller), then join it to put it back into string form.
So, if our current word were “bag”, this would give us “abg”.
So, now we have our desired alphabetized string, we need to make it into an object key.
However, maybe “gab” was earlier in our words array, and our anagrams object already has a key of “abg”. We need to check to see if a matching key already exists, then, if not, create it.
A nice thing about working with object keys is that, using square brackets, you can look them up by variable name. So if the current word were “gab”, and the variable letters, by extension, was assigned the value “abg”, then looking up anagram[letters] would give us the same data as anagram.agb or anagram[“agb”]. This will allow us to get the value “gab” by looking up any of the above three references.
My favorite way to do this is to say that anagrams[letters] is equal either to itself (if it already exists) or to an empty array. Creating an empty array where we can store our anagrams right off the bat can save some irritating bugs caused by accidentally storing values as the wrong data type (say, by saving a word as a string, then trying to add another anagram to that string later).
Okay, now we have an alphabetized list of letters and an array waiting to be filled with anagrams. So, we push our current word into that array, and continue on to the next iterative loop. If the next word is not an anagram of any previous words, a new key-value pair will be created. If it is, it will be pushed into the value array paired with the key which matches its alphabetized list of letters.
Now, hopefully, when this loop resolves we’ll have a hash full of nicely organized anagrams.
Now, according to our pseucode, we want to push the arrays of anagrams into our collectedAnagrams container array.
This requires us to iterate through our anagrams object.
To do that, I prefer to use a for/in loop, which allows us to iterate over each key in the object.
By placing the variable we assign the value of the current key in square brackets, we can look up the value paired with it, and push that array of anagrams into the collectedAnagrams array.
Finally, we can return our collection of anagrams.
Let’s throw this into the console and see what it returns:
🌟 Great! It’s tackled a nice array of possible anagrams, and returned us an array containing all the original strings, now collected into subarrays of anagrams.
I’ve seen some variations of this challenge that ask the programmer to identify and remove any anagrams from an array of strings, purportedly in the interest of removing superfluous data. If you wished to do so, you could remove all the subarrays with length > 1, thereby effectively removing all anagrams from the original array.
If you’d like to see more solutions using this approach, you might enjoy Solving the Two-Sum Problem in Javascript, Three Ways, where you can explore the relative efficiency of a hash-based solution compared to its alternatives!
N.B. — I’ve been in Covid-19 quarantine in NYC, so I’ve kept things a bit more brief than usual this week. I did still enjoyed working out a solution to this challenge, and look forward to diving deeper into other challenges in the future.
