[LeetCode] 49. Group Anagrams

Table of Contents

Description

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

Note: An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

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

Constraints:

• $1 \leq \text{strs.length} \leq 10^4$
• $0 \leq \text{strs}[i].\text{length} \leq 100$
• strs[i] consists of lowercase English letters.

Approach

Group anagrams by converting each word to a canonical form (sorted characters) and using a hash map to collect words with the same form.

Solution

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  // store grouped anagrams with sorted string as key
  const map = new Map();

  strs.forEach(str => {
    // Sort the characters of the string to create a normalized key
    // Anagrams will have the same sorted key
    const key = str.split("").sort().join("");

    // If the key is not in the map, initialize with an empty array
    if (!map.has(key)) map.set(key, []);

    // Add the original string to the array corresponding to the sorted key
    map.get(key).push(str);
  });

  // Convert the map values (arrays of anagrams) into an array and return
  return Array.from(map.values());
};

Complexity Analysis

Time Complexity

The time complexity is $O(nk \log k)$, where $n$ is the number of strings and $k$ is the maximum length of a string. This comes from sorting each string and processing all $n$ strings.

Space Complexity

The space complexity is $O(nk)$, since we use a hash map to store up to $n$ groups and each string can have up to $k$ characters.