Group Anagrams

Problem

Let’s take a look at the question,

Given an array of strings strs, group the together. You can return the answer in any order.

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

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

Click on the above card to go to the problem on LeetCode.

Approach

ngl this one made my brain tired.

It took me a while before I kinda figured it out. Had some help tho.

There’s no way I would’ve figured this out if I was presented with this for the first time in an interview.

Let’s look at how we should approach this.

We are once again going to use a hashmap.

Initialize a hashmap

pretty important imo

iterate over each word in the list

we’re gonna iterate over each word to sort it.

sort the word

user sorted() function to sort the word.

we are sorting so we can identify the anagram easily.

tan, ant when sorted become ant. so, we can easily identify the fellow anagram buddies.

use hashmap

once sorted, check if the sorted word exists in the hashmap.

if yes, then append the original unsorted word to that key.

if no, then create a new key and add the value in a list (important to add the value in a list format so we can append other matching elements).

return all values

finally once we’ve gone through all the words in the list, we can now just return the values.

since we added all the values in a list format, they are already how we want them to be.

just return all the values enclosed in a list and we are done.

Solution

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagram_groups = {}

        for word in strs:
            sorted_word = "".join(sorted(word))

            if sorted_word in anagram_groups:
                anagram_groups[sorted_word].append(word)
            else:
                anagram_groups[sorted_word] = [word]

        return list((anagram_groups.values()))

This is again a medium level question.

We’re using a hashmap and lists to solve this.

The approach is pretty good too.