Group all anagrams together

Medium

Problem

Given a list of words, group together the words that are anagrams of each other (same letters, rearranged). Return the groups in any order.

Example 1

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

Also asked as: Given a sequence of words, print all anagrams together

Test cases

Case 1

Input:    ["eat","tea","tan","ate","nat","bat"]
Expected (any order): [["eat","tea","ate"],["tan","nat"],["bat"]]

Case 2

Input:    [""]
Expected (any order): [[""]]

Case 3

Input:    ["a"]
Expected (any order): [["a"]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Bucket by sorted characters

Time O(n · k log k)Space O(n · k)

Two words are anagrams iff their sorted-letter strings match; use that as a map key.

function groupAnagrams(words) {
const groups = new Map();
for (const w of words) {
const key = [...w].sort().join('');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(w);
}
return [...groups.values()];
}

Use a 26-length count vector as the key to drop the sort → O(n·k).