medium

Group Anagrams

Group words that are rearrangements of each other by filing every word in a hash map under the sorted letters that form its signature.

1. Define the problem

Group Anagrams

Given an array of strings strs, group together all the words that are anagrams of each other . Return the groups as an array of arrays, in any order. The trick is to give every word a signature that is the same for all its anagrams. Sorting the letters of a word does exactly that: "eat", "tea" and "ate" all sort to "aet". Use a hash map whose key is the sorted signature and whose value is the list of words that produced it. Every word is filed under its signature in one pass.

Constraints

  • 1 ≤ strs.length ≤ 104
  • 0 ≤ strsi.length ≤ 100
  • strsi consists of lowercase English letters
  • The groups may be returned in any order

Example

Inputstrs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Explanation eat, tea and ate all sort to "aet" so they share a group. tan and nat both sort to "ant". bat is alone under "abt".

2. Know the words first

In plain terms

Anagram
A word made by rearranging all the letters of another word, using each letter the same number of times.
Signature key
A small value worked out from an item that is identical for every item that belongs in the same group. Here it is the letters of the word put in alphabetical order.
Bucketing
Filing items into named piles held in a hash map, so that related items end up in the same pile without comparing every pair.
3. Visualize the solution

One cell per hash map key, label = sorted signature, value = group size

One cell per hash map key, label = sorted signature, value = group size
Statusinit

The map starts with no piles at all.

What happens in this step

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
groups = empty

The three cells stand for the three signatures this input will produce.
A dash means that pile does not exist yet.
Step 1 of 6

Steps to visualize

  1. Each cell is one key in the hash map. The label is the sorted signature and the value is how many words are filed under it.
  2. Take each word in turn and sort its letters to build the signature.
  3. If that signature has no pile yet, start an empty one.
  4. Add the word to the pile for its signature.
  5. When every word is filed, the answer is the list of piles.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per hash map key, label = sorted signature, value = group size
Statusinit

The map starts with no piles at all.

What happens in this step

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
groups = empty

The three cells stand for the three signatures this input will produce.
A dash means that pile does not exist yet.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function groupAnagrams(strs) {
  const groups = new Map();

  for (const word of strs) {
    const key = word.split('').sort().join('');

    if (!groups.has(key)) {
      groups.set(key, []);
    }

    groups.get(key).push(word);
  }

  return Array.from(groups.values());
}
Time
O(n * k log k) for n words of length k
Space
O(n * k)
6. Test cases

Test cases

InputExpectedCovers
strs = ["eat", "tea", "tan", "ate", "nat", "bat"][["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]example from the description
strs = [""][[""]]the empty string still gets a signature and a pile
strs = ["a"][["a"]]one word alone in its group
strs = ["abc", "def", "ghi"][["abc"], ["def"], ["ghi"]]nothing groups together, so every pile has one word
strs = ["aab", "aba", "baa", "ab"][["aab", "aba", "baa"], ["ab"]]letters repeat, and a shorter word is not an anagram of them
strs = ["listen", "silent", "enlist", "google", "banana"][["listen", "silent", "enlist"], ["google"], ["banana"]]longer words with one big group and two singles

Keep reading