Group Anagrams
Today I will talk about a very interesting question and concept that often comes up on technical interviews. It’s been reported that Amazon, Microsoft, Facebook, and many other companies ask Anagram questions on interviews.
I will try to explain the solution using Javascript. However, before we dive into problem-solving, let’s explain what Anagram is.
By definition, “an anagram is a word or phrase that is made by rearranging the letters of another word or phrase.” In other words, taking one word or phrase and changing the order of its characters to produce a new word or phrase. For example: study = dusty, cat= act. If you are a Harry Potter fan, you will remember that Lord Voldemort’s actual name is an anagram of his birth name.
The question I am going to use is from Leetcode:
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]Note:
- All inputs will be in lowercase.
- The order of your output does not matter.
It’s important to note:
1. Anagram words share the same characters;
2. Anagram words share the same amount of characters;
These two concepts help us to think about grouping and how is it possible to compare the same characters of words/phrase that has the same length.
One way of solving this problem is to take every string from the array, “split” them by characters (‘eat’ = ‘e’, ‘a’, ‘t’), sort alphabetically, join back, and compare them with another words’ set of characters.
However, the next challenge is to appropriately place or categorize word that has anagrams. For this, we are going to use Hash which will help us create strings as keys, and values as arrays of appropriate words/anagrams.
To visualize it:
const hash = {
[
"aet": ["ate","eat","tea"],
"ant": ["nat","tan"],
"abt": ["bat"]
]
}1 . To start we create empty hash:
const hash = {}2. Loop over the array to get each string or word from the array and sort them alphabetically.
3. Next let's start constructing our hash. First we are checking if our hash has key. If it does not have the key, then assign it to our hash with the corresponding strings as values. Otherwise, we push string values inside corresponding keys.
4. Finally, our hash is going to look like this:
const hash = {
[
"aet": ["ate","eat","tea"],
"ant": ["nat","tan"],
"abt": ["bat"]
]
}However, we will only need to return hash values, which is done like so:
and our return is going to be:
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]The whole code:
Resources:
