49. Group Anagrams

Medium

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.

Examples

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"]]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def groupAnagrams(strs: List[str]) -> List[List[str]]:
    anagrams = defaultdict(list)
    
    for s in strs:
        # Sort characters to create key
        key = ''.join(sorted(s))
        anagrams[key].append(s)
    
    return list(anagrams.values())

Java Solution


class Solution {
    public List> groupAnagrams(String[] strs) {
        Map> anagrams = new HashMap<>();
        
        for (String s : strs) {
            // Sort characters to create key
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            
            anagrams.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(anagrams.values());
    }
}

C++ Solution


class Solution {
public:
    vector> groupAnagrams(vector& strs) {
        unordered_map> anagrams;
        
        for (const string& s : strs) {
            // Sort characters to create key
            string key = s;
            sort(key.begin(), key.end());
            anagrams[key].push_back(s);
        }
        
        vector> result;
        for (const auto& pair : anagrams) {
            result.push_back(pair.second);
        }
        
        return result;
    }
};

JavaScript Solution


/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const anagrams = new Map();
    
    for (const s of strs) {
        // Sort characters to create key
        const key = [...s].sort().join('');
        if (!anagrams.has(key)) {
            anagrams.set(key, []);
        }
        anagrams.get(key).push(s);
    }
    
    return Array.from(anagrams.values());
};

C# Solution


public class Solution {
    public IList> GroupAnagrams(string[] strs) {
        var anagrams = new Dictionary>();
        
        foreach (string s in strs) {
            // Sort characters to create key
            char[] chars = s.ToCharArray();
            Array.Sort(chars);
            string key = new string(chars);
            
            if (!anagrams.ContainsKey(key)) {
                anagrams[key] = new List();
            }
            anagrams[key].Add(s);
        }
        
        return anagrams.Values.ToList();
    }
}

Complexity Analysis

Solution Explanation

This solution uses a hash map to group anagrams together. Here's how it works:

Key points: