Group anagrams

• medium
• Problem URL

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.

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

Solution

Use a hash table to store the anagrams. For each string, sort the characters and use the sorted string as a key in the hash table. Add the original string to the array of anagrams for that key. Finally, return the values of the hash table as an array.

Implementation

JavaScript

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const anagrams = new Map();
    for (const s of strs) {
        const sortedWord = s.split("").sort().join("");
        const wordAnagrams = anagrams.get(sortedWord) ?? [];
        wordAnagrams.push(s);
        anagrams.set(sortedWord, wordAnagrams);
    }
    return Array.from(anagrams.values());
};

TypeScript

function groupAnagrams(strs: string[]): string[][] {
    const anagrams = new Map<string, string[]>();
    for (const s of strs) {
        const key = s.split("").sort().join("");
        const wordAnagrams = anagrams.get(key) ?? [];
        wordAnagrams.push(s);
        anagrams.set(key, wordAnagrams);
    }
    return Array.from(anagrams.values());
}

Go

import "sort"

func groupAnagrams(strs []string) [][]string {
    anagrams := make(map[string][]string)
    for _, s := range strs {
        bytes := []byte(s)
        sort.Slice(bytes, func(i, j int) bool { return bytes[i] < bytes[j] })
        key := string(bytes)
        anagrams[key] = append(anagrams[key], s)
    }

    values := make([][]string, 0)
    for _, v := range anagrams {
        values = append(values, v)
    }

    return values
}

Python

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagram_group = defaultdict(list)

        for word in strs:
            sorted_word = "".join(sorted(word))
            anagram_group[sorted_word].append(word)

        return list(anagram_group.values())

C++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        std::unordered_map<string, vector<string>> anagram_group;
        for (const string& str : strs) {
            string sorted_key = str;
            sort(sorted_key.begin(), sorted_key.end());
            anagram_group[sorted_key].push_back(str);
        }

        vector<vector<string>> result;
        for (auto& pair : anagram_group) {
            result.push_back(pair.second);
        }
        return result;
    }
};

Java

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> m = new HashMap<>();
        for (String item : strs) {
            char[] charArr = item.toCharArray();
            Arrays.sort(charArr);
            String key = new String(charArr);
            m.computeIfAbsent(key, k -> new ArrayList<>()).add(item);
        }
        return new ArrayList(m.values());
    }
}