## DEV Community is a community of 796,806 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Posted on

# 30-Day LeetCoding Challenge: Group Anagrams

## Solution:

First of all, do you know what is anagram, in short, two string are anagrams if and only if their sorted strings/letters are equal?

So from the definition above, we can figure out a simple solution to do. We can think of that we need to maintain a list of each word and any other word that their sorted letters are equal.

The best data structure can help us with doing this is hash map by making `key: value` pairs which are the `key = the sorted string` & the `value = list of the corresponding words that equal to this sorted key`

Let's see an example to make it more clear.

• Example:

`words = ["eat", "tea", "tan", "nat"]`

1. so we need hash-map will call it `anagrams = {}`.

2. our first word is `word = 'eat'` we need to sort it so it will be `key = sorted(word) = sorted('eat') = 'aet'`

3. add to the hash-map as a key and the original word as value:
`anagrams[key] = [word]`

So, our map looks like this now: `anagrams = {'aet': ['eat']}`

1. check the second `word = 'tea'` the sorted one is `key = sorted('tea') = 'aet'`, ooh we already have this key in our map so update it is values with this new word so our map will be: `anagrams = {'aet': ['eat', 'tea']}`

Then will keep doing this with the other two words and finally will have this map:
`anagrams = {'aet': ['eat', 'tea'], 'ant': ['tan', 'nat']}`

The list step just print the map values as our answer so our answer will be:

`anagrams.values() = [['eat', 'tea'], ['tan', 'nat']]`

• Pseudocode:
``````1. define our map anagrams = {}
2. loop for each word in words
3.    build the key = "".join(sorted(word))
4.    add the word to the key value list or create new key with this word (anagrams[key] = anagrams.get(key, []) + [word])
5. return anagrams.values()
``````
• Complexity:

• Time complexity:

• We have one loop over our words list so it is O(n) where n is the number of words.
• We also do in each iteration sorting which will be O(klog(k)) where k is the maximum length of a word in words list. So total will be O(nklog(k))
• Space complexity: will be O(nk) the data we store in the map

Solution in python

There is another way to solve this problem try to find it out :).

## Discussion (2)

Muhimen

It's good that you are taking the leetcode 30 days April challenge and spreading your knowledge among those who don't know. But publishing problems before the competition is ended is illegal. It will be nice if you publish your posts after a day the problem expires. For example, you could have published this post after the day 7 challenge. It would be really nice for you.
Thanks for understanding.
And always remember: We need programmers not copiers. Wish you all the best for the upcoming challenges. ðŸ˜‰