Rough at Sea

Group Anagrams

This is problem #4 in NeetCode's Arrays & Hashing section of problems.

Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Example 1:

Input: strs = ["act","pots","tops","cat","stop","hat"]

Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]

Example 2:

Input: strs = ["x"]

Output: [["x"]]

Example 3:

Input: strs = [""]

Output: [[""]]

The code is stubbed out as follows:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

Below is the solution that lives rent free in my head:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for istr in strs:
            key = ''.join(sorted(istr))
            if key in groups:
                groups[key].append(istr)
            else:
                groups[key] = [istr]
        
        return list(groups.values())

As usual, the insight to solving this was not my own. We saw previously that if two strings are anagrams, then sorting them and checking if they are equal is a really fast way to determine if they are anagrams of each other.

This is the reason why we say that key = sorted(istr). The only reason we join it with an empty string is to cast its type from list to string. Hence why we have key = ''.join(sorted(istr)). Now we can use the sorted version of each string as the key, and then just add strings to the corresponding array as we encounter them.

In the example where strs = ["act","pots","tops","cat","stop","hat"], the loop will proceed as follows:

istr = "act"
key = sorted(istr) = "act"
groups[key] does not exist, so we short circuit to the `else` case. We create a new array with one element, i.e., ["act"]
groups = { "act": ["act"] }

istr = "pots"
key = sorted(istr) = "opst"
groups[key] does not exist, so we short circuit to the else case. We create a new array with one element, i.e., ["opst"]
groups = { "act" : ["act"], "opst": ["pots"] }

istr = "tops"
key = sorted(istr) = "opst"
groups[key] does exist from when istr was equal to "pots". In this case we append "tops" to the groups["opst"] array.
groups = { "act" : ["act"], "opst": ["pots", "tops"] }

istr = "cat"
key = sorted(istr) = "act"
groups[key] does exist from when istr was equal to "act". In this case we append "cat" to the groups["act"] array.
groups = { "act" : ["act", "cat"], "opst": ["pots", "tops"] }

istr = "stop"
key = sorted(istr) = "opst"
groups[key] does exist from when istr was equal to "pots". In this case we append "stop" to the groups["opst"] array.
groups = { "act" : ["act", "cat"], "opst": ["pots", "tops", "stop"] }

istr = "hat"
key = sorted(istr) = "aht"
groups[key] does not exist, so we short circuit to the else. We create a new array with one element, i.e., ["hat"].
groups = { "act" : ["act", "cat"], "opst": ["pots", "tops", "stop"], "aht": ["hat"] }

Finally, we simply return groups.