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 bee1a1t1
. - 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
Top comments (3)
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!
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.
Make sense, just curious what is the complexity of the array logic? it would be really helpful if you can add that too