21. Group anagrams

Task

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.

Leetcode problem link

Example:

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

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

Comments

This algorithms can be solved by reducing each string to the letters it is composed of and then connecting each set of letters with the strings that contain exactly those letters. The data structure that can do that is a hash map.

There are two approaches:

• sorting the letters in each string before adding it to the hash map, so that they can be grouped together
• using an array composed of the 26 letters between a-z and count the occurrences of each letter, then mapping the hash using this array

Sorting solution

var groupAnagrams = function (strs) {
  let hash = {};

  strs.forEach((str) => {
    const letters = str.split("").sort();

    hash[letters] ? hash[letters].push(str) : (hash[letters] = [str]);
  });

  return Object.values(hash);
};

Time Complexity: O(log n * m)

Where m is the average length of the strings

Space Complexity: O(n)

Mapping character count of each string

var groupAnagrams = function (strs) {
  let hash = {};

  strs.forEach((str) => {
    let count = new Array(26).fill(0);

    // 97 is the numeric value of the character 'a', so if you subtract 97 from a character between 'a' and 'z', you are mapping that character to an index of your array between 0 and 25
    for (let char of str) count[char.charCodeAt() - 97]++;
    let key = count.join("#");
    hash[key] ? hash[key].push(str) : (hash[key] = [str]);
  });

  return Object.values(hash);
};

Time Complexity: O(m * n)

Where m is the total number of strings that we are given and n is the average length of a string

Space Complexity: O(n)