49. Group Anagrams Medium

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

Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

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

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

Approach

Input: An array of strings strs

Output: Group strings that use the same characters together and return a new array

This is a Hash Table problem.

We can iterate through the string array while using the alphabetically sorted version of each string as a key.

In this way, strings that use the exact same letters will generate the same key.

Store the strings with the same key in a hash table, and finally export a new array.

Implementation

python

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Use defaultdict(list) to store grouped results
        # key: sorted string (acting as a "character feature")
        # value: all words belonging to this feature
        anagram_map = defaultdict(list)
        
        # Iterate through each word
        for word in strs:
            # Sort the letters of the word, using it as the "unique identifier for the group"
            # For example, "eat" -> "aet", "tea" -> "aet"
            sorted_word = ''.join(sorted(word))
            
            # Put the original word into its corresponding group
            anagram_map[sorted_word].append(word)
        
        # Return all grouping results (only values are needed)
        return list(anagram_map.values())

javascript

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map();

    for (let s of strs) {
        const key = s.split('').sort().join('');
        if (!map.has(key)) map.set(key, []);

        map.get(key).push(s);
    }

    return Array.from(map.values());
};

Complexity Analysis

• Time Complexity: O(n * k log k) where n is number of strings, k is max string length
• Space Complexity: O(n * k)

Links

49. Group Anagrams (English)49. 字母异位词分组 (Chinese)