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.

Constraints:

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

Example:

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

(The order of the inner lists and the strings within those lists does not matter.)

Solution

Approach:

The core idea is that anagrams will have the same sorted form. For example, "eat", "tea", and "ate" all become "aet" when sorted alphabetically.

  1. Use a Hash Map: We'll leverage a hash map (or dictionary) to store our groups.
    • The key for the hash map will be the sorted version of a word.
    • The value will be a list of all original words that produce that specific sorted key.
  2. Iterate and Categorize:
    • Go through each string s in the input array strs.
    • For each s, convert it into its canonical form by sorting its characters. A common way is to convert the string to a list of characters, sort the list, and then join it back into a string (e.g., "".join(sorted(s))).
    • Use this sorted string as the key to anagram_groups.
    • Append the original string s to the list associated with this key.
  3. Collect Results: Once all strings have been processed, the values of the hash map will be the desired groups of anagrams. Convert these values into a list to get the final output.

Python Code:

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        # defaultdict allows us to append to a list without checking if the key exists yet
        anagram_groups = defaultdict(list)

        for s in strs:
            # Sort the string to get a canonical key. 
            # For example, "eat", "tea", "ate" all become "aet".
            sorted_s = "".join(sorted(s))
            
            # Add the original string to the list corresponding to its sorted key
            anagram_groups[sorted_s].append(s)
        
        # The values of the dictionary are the lists of anagrams
        return list(anagram_groups.values())