DEV Community

loading...

Group Anagrams Python Solution

Justin Bermudez
・2 min read

Link to leetcode problem here

The problem states:
Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Initial Thoughts

The first thing we should think of is how to tell if any given word is an anagram of another. Looking at each letter in a word might be a start for our solution. But going through each letter and figuring out if 2 words have the same letters might take too long.

What if we sorted each letter in a word alphabetically. This can point out to us words that have the same letters and are anagrams.

The best way to sort the words out would be with a sort method. in python you are able to just do it on the word itself
sortedWord = "".join(sorted(word))
Other languages may not be so kind.

Now that we can arrange every word to sort within itself, we can then group up the words that are sorted to be the same.
Words like "eat, tea, ate" will all be sorted to the same "aet".

This is not our whole solution though since the problem is called "group anagrams." How would we store all these separate groups?

Well since we know the words "eat, ate," and "tea" all get sorted to "aet". What if we group them to that sorted word in a hash table or dictionary.
The dictionary would then look something like

table = {
    "aet": ["ate", "eat", "tea"]
}

We would then be able to check any word if they are anagrams of each other. If for instance we get a different word such as "car".
"".join(sorted(car)) => acr

which is not the same as "aet" therefore is not an anagram of the other words.

Since we have a new word then we can add it to our table as a new key value pair

table = {
    "aet": ["ate", "eat", "tea"],
    "acr": ["car"]
}

This is the general pattern until we go through the whole input array of words.

The problem asks us to return the list of anagrams together in one big array. We can then return with list(table.values()) in python which would return all the values of our table in a list of arrays with anagrams.

def groupAnagrams(words):
    anagrams = {}
    for word in words:
        sortedWord = "".join(sorted(word))
        if sortedWord in anagrams:
            anagrams[sortedWord].append(word)
        else:
            anagrams[sortedWord] = [word]
    return list(anagrams.values())

Discussion (0)