Group Anagrams

Patrick Leaton
Published: March 16, 2021, 4:02 a.m.
Problem Description

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.

 

Example 1:

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

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

 

Constraints:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lower-case English letters.

 

The description was taken from https://leetcode.com/problems/group-anagrams/.

Problem Solution

#O(N(K(log(K)))) Time, O(N*K) Space
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        seen = {}
        for word in strs:
            sorted_word = "".join(sorted(word))
            if sorted_word in seen:
                seen[sorted_word].append(word)
            else:
                seen[sorted_word] = [word]
        return seen.values()

Problem Explanation

The problem requires us to group any anagram we see within the input array.

Two or more words are anagrams if the characters could be rearranged to become the same word.  This means that if the characters had the same frequency, then sorting characters of two or more anagrams would result in the same word.

Knowing this, we can traverse the input array of words and sort each word we see.  If we find a sorted word that has been seen already, that means that the word is an anagram to a previous word, so we can group these words together by using the sorted version of each word as a key to a hashmap we will create.

Once we finish grouping the words, we will just need to return the values of the hashmap.

We will start by initializing our hashmap of words that we have seen.

        seen = {}

 

Next, let's traverse the strings and in each iteration, sort the word.  

Python's sorted function returns a string in an array format, so we will enclose that function call within a join operation that will group the array of characters back into a string.

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

 

Now we'll check if the sorted word is in the dictionary already.  If it is, we will append our unsorted word to the group of anagrams that share the same sorted value.

            if sorted_word in seen:
                seen[sorted_word].append(word)

 

Otherwise, we will set the sorted word as a new key in the dictionary with the unsorted word as its initial value.  

            else:
                seen[sorted_word] = [word]

 

Once we have put all our words in the dictionary we will just need to return the values.  These will be our grouped anagrams. 

        return seen.values()