Grouping Anagrams Together in JavaScript
In my experience, a lot of the time we spend with work, both in cyber space and real space, is in making the result look just right.
In this post, we’ll go over a solution to Leetcode’s Group Anagram problem, where most of the difficulty is outputting the result in a very specific way.
The problem statement is simple: given a bunch of strings in an array, group all the anagrams of each other together in arrays. So, for example, if we have an array called strs (for strings) like [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], the result would look like ,
["ate","eat","tea"],
["nat","tan"],
["bat"]
We don’t have to worry about order, case, or special characters. Let’s dive into the solution below
First, let’s remind ourselves what an anagram is: a word that has the same amount of letters as another word. So, like in the picture above, “listen” is an anagram of “silent”.
An easy way to test if two words are anagrams of each other is by doing this:
return
word1.split("").sort().join("") === word2.split("").sort().join("")Using “listen” as our first word, and “silent” as our second word, this code does the following:
- Creates an array, and splits each character of the word to elements in this array separated by nothing, and returns that array. So now word1 is [“l”, “i”, “s”, “t”, “e”, “n”] and word2 is [“s”, “i”, “l”, “e”, “n”, “t”]
- Sorts each element of the array in ascending order by default. So now word1is [“e”, “i”, “l”, “n”, “s”, “t”] is [“e”, “i”, “l”, “n”, “s”, “t”]
- Joins all the elements of the array together, with nothing separating the elements. So now word1 is “eilnst” and word2 is “eilnst”.
- Are these two the same? Yes! So this will evaluate to true
Because anagrams have the same amount of letters, once they’re sorted, the strings should equal one another. And because our problem tells us we don’t need to worry about special characters, or case, this is a straightforward way to evaluating if a word is an anagram of another.
Now that we have a way to test whether or not a word is anagram of one another, all we have to do is group them in a particular way. This is the more complex portion of the algorithm. Here’s the full solution:
function groupAnagrams(strs) {
let result = {};for (let word of strs) {
let cleansed = word.split("").sort().join("");
if (result[cleansed]) {
result[cleansed].push(word);
} else {
result[cleansed] = [word];
}
}return Object.values(result);
}
While small, there’s a mighty’ lot happening here. Let’s iterate through it with some of our examples: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”];
First, we initialize an object or hash called result. Here’s where we’ll place our results. Then, for each word (element) of the strs array, we perform the “cleansing” of the word explained above to make it ready to test if its an anagram. So “eat” is now “aet”.
Next, we do some conditional checks that are designed to prep our data in the format we need it. First we want to check if the word we’ve cleansed is already in our result object (i.e. it might be an anagram of a word we’ve already iterated through), so for “aet”:
- If I look for “aet” in the result object, and it returns a truthy value, then we’ll just push into that result (which will be an array) the current word we’re iterating (“eat”).
- If not, which in this first case nothing will be in there, we’ll add the cleansed word as a key, and the original word as its value in the form of array with the word (“eat”) as its first element.
We do this for every word…next is “tea”
- We “cleanse” it and make it “aet”
- Does looking for a value of “aet” give me a truthy? It does! Let’s get that value (which is an array), and push word (“tea”) in there. Now the object looks like this:
result = {
aet: ["eat", "tea"]
}One more time. We iterate with “tan”. After cleansing, it’s “ant”. Is “ant” in the result hash? It’s not! So we add the cleansed word as a key, and the original word as an array with the word (“tan”) inside of it as its first element. Now the result hash looks like this:
result = {
aet: ["eat", "tea"],
ant: ["tan"]
}After iterating through all the words in the strs array, the result hash will look like this:
result = {
aet: ["eat", "tea", "ate"],
ant: ["tan", "nat"],
abt: ["bat"]
}Now, we just need to return all the groupings. Notice, they’re all the values in our key:value object. So we return it with Object.values(result) and we’re done!
Thanks for reading!
And remember: grit > talent.
