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"]]

Solution

Approach:

  • Canonical Form: The core idea is that anagrams have the same characters with the same frequencies. If we can find a canonical representation for each string, then all anagrams will map to the same form.
  • Sorting as Canonical Form: A simple and effective way to achieve this is by sorting the characters of each string. For example, "eat", "tea", and "ate" all become "aet" when sorted.
  • Data Structure: We use a hash map (or dictionary) to store the groups. The sorted string (canonical form) will be the key, and the value will be a list of original strings that are anagrams of each other.

Algorithm:

  1. Initialize an empty hash map, say anagram_groups, where keys are strings and values are lists of strings.
  2. Iterate through each string s in the input array strs.
  3. For each string s, convert it into a character array, sort the array, and then join it back into a string. Let's call this sorted_s.
  4. Use sorted_s as the key to look up in anagram_groups. Append the original string s to the list associated with sorted_s.
  5. If sorted_s is not yet a key, create a new entry with sorted_s as the key and a new list containing s as its initial value.
  6. After processing all strings, the values of anagram_groups will be the desired lists of grouped anagrams.

Example Implementation (Python):

import collections

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        # Use a defaultdict to automatically create a list for a new key
        anagram_map = collections.defaultdict(list)

        for s in strs:
            # Sort the string to create a canonical key
            # Example: "eat" -> "aet"
            sorted_s = "".join(sorted(s))
            
            # Append the original string to the list corresponding to its sorted form
            anagram_map[sorted_s].append(s)

        # Return the values (lists of anagrams) from the map
        return list(anagram_map.values())