Group anagrams

• medium
• hash table
• 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 sortedWord = s.split("").sort().join("");
    const wordAnagrams = anagrams.get(sortedWord) ?? [];
    wordAnagrams.push(s);
    anagrams.set(sortedWord, 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] })
    hash := string(bytes)
    anagrams[hash] = append(anagrams[hash], 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;
    }
};

Pseudocode

1. Create a map to store the anagrams.
2. Loop through each string in the input array.
3. Sort the string and use it as a key in the map.
4. Add the string to the array of anagrams for the key.
5. Return the values of the map as an array.

Complexity Analysis

• The time complexity of this algorithm is O(n _ m _ log(m)), where n is the number of strings and m is the length of the longest string. This is because we are sorting each string.

• The space complexity of this algorithm is O(n * m), where n is the number of strings and m is the length of the longest string. This is because we are storing the anagrams in a map.