DEV Community

Bibin Jaimon
Bibin Jaimon

Posted on

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"]]
Enter fullscreen mode Exit fullscreen mode

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"]
}
Enter fullscreen mode Exit fullscreen mode
  • 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]
Enter fullscreen mode Exit fullscreen mode
  • 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 ]
Enter fullscreen mode Exit fullscreen mode
  • 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

Top comments (3)

Collapse
 
nikhilunni511 profile image
Nikhil Unni V P • Edited

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!

Collapse
 
bibinjaimon profile image
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.

Collapse
 
nikhilunni511 profile image
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