Array & Hashing: Group Anagrams

How to group anagrams in same group?

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Anagram mean that the words will have same length and same number of character occurrence.

eat can be rearranged to tea, ate

My Recommended Solution

• Lets take eat for example.
• Count the number of characters in it. That would be e = 1, a = 1, t = 1. So the key for eat would be e1a1t1.
• We need to find other words which having same key.
• In this case we can store this to a data structure called Hash Map. Then the key of the hash map will be the one which we create with number of characters of the word and value will be an Array.
• Once we created a key then we can add it to the hash map. Then the result would like this

{
"e1a1t1": ["eat"]
}

• In this case getting the key's character order is a challenging thing. What I'm suggesting is to create an array with 26 size (number alphabets).
• Initialize it with zero

[0,0,0,0,0,....0,0,0,0]

• We can use this array to create a key. Which should be equal for word with same number of characters.
• For Example, if we take eat. Then the array will looks like,

[ 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ]

• From this we can create a key by stringifying the array '1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0'

How do we know the index in the array to increment the count of a particular character?

Every alphabets has an ASCII value.
a => 97, for e => 101, t => 116

If you closely look at this numbers, We can see a way to get the corresponding array index. Find it.

After looping through every words we will have a hash map with grouped anagrams. The values of all the keys of the hash map is the answer.

Happy Coding,
Bibin Jaimon

Comments

[Nikhil Unni V P]

Great work!
Just a small doubt: how about using the sorted word itself as a key?
for eg: {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}
Keep up the good work!

[Bibin Jaimon]

The issue with this approach is you will have to perform a sort operation in all the other strings. So, that would not be a good solution in terms of time complexity.

[Nikhil Unni V P]

Make sense, just curious what is the complexity of the array logic? it would be really helpful if you can add that too