Group Anagrams
On this page 
Problem Statement Solution 1: Sorting-Based Approach Solution 2: Frequency Count Approach Solution 3: Hashing with Sorted Characters Approach Solution 4: Bit Masking Approach Solution 5: Canonical Form Approach Solution 6: Sorted Tuple Key Approach Solution 7: Regular Expression Approach More Problems Solutions
Problem Statement
Imagine you have a list of words, and you want to group them into sets where each set contains words that are anagrams of each other.
What’s an Anagram?
An anagram is a word formed by rearranging the letters of another word. For example, "tea" and "eat" are anagrams because you can rearrange the letters of "tea" to get "eat."
Your Task:
Given an array of words, group all the anagrams together. Each group of anagrams should be in its own sub-array. The order of the groups and the order of words within each group doesn’t matter.
Example 1
Input: array = ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
Example 2
Input: array = [""]
Output: [[""]]
Example 3
Input: array = ["a"]
Output: [["a"]]
Constraints
Each word in the list is non-null and contains only lowercase letters.
Your solution should efficiently handle large lists and long words.
Solution 1: Sorting-Based Approach
function groupAnagrams_Sorting(strs) {
const map = new Map();
for (const str of strs) {
// Sort the characters of the string
const sortedStr = str.split('').sort().join('');
// Use sorted string as a key and group the anagrams
if (!map.has(sortedStr)) {
map.set(sortedStr, []);
}
map.get(sortedStr).push(str);
}
// Convert the map values to an array of arrays
return Array.from(map.values());
}
const array1 = ["eat","tea","tan","ate","nat","bat"];
groupAnagrams_Sorting(array1); //output: [["eat","tea","ate"],["tan","nat"],["bat"]]
const array2 = [""];
groupAnagrams_Sorting(array2); //output: [[""]]
const array3 = ["a"];
groupAnagrams_Sorting(array3); //output: [["a"]]
Solution 2: Frequency Count Approach
function groupAnagramsFrequency(words) {
const anagramGroups = new Map();
words.forEach(word => {
const frequencyCount = Array(26).fill(0); // Frequency count for each letter
for (const char of word) {
frequencyCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
const key = frequencyCount.join('#'); // Use the frequency array as a key
if (!anagramGroups.has(key)) {
anagramGroups.set(key, []);
}
anagramGroups.get(key).push(word);
});
return Array.from(anagramGroups.values());
}
const array1 = ["eat","tea","tan","ate","nat","bat"];
groupAnagramsFrequency(array1); //output: [["eat","tea","ate"],["tan","nat"],["bat"]]
const array2 = [""];
groupAnagramsFrequency(array2); //output: [[""]]
const array3 = ["a"];
groupAnagramsFrequency(array3); //output: [["a"]]
Solution 3: Hashing with Sorted Characters Approach
function groupAnagramsHashing(words) {
const anagramGroups = new Map();
words.forEach(word => {
const sortedCharacters = word.split('').sort().join('');
if (!anagramGroups.has(sortedCharacters)) {
anagramGroups.set(sortedCharacters, []);
}
anagramGroups.get(sortedCharacters).push(word);
});
return Array.from(anagramGroups.values());
}
const array1 = ["eat","tea","tan","ate","nat","bat"];
groupAnagramsHashing(array1); //output: [["eat","tea","ate"],["tan","nat"],["bat"]]
const array2 = [""];
groupAnagramsHashing(array2); //output: [[""]]
const array3 = ["a"];
groupAnagramsHashing(array3); //output: [["a"]]
Solution 4: Bit Masking Approach
function groupAnagramsBitMasking(words) {
const anagramGroups = new Map();
function computeBitMask(word) {
let mask = 0;
for (const char of word) {
mask ^= 1 << (char.charCodeAt(0) - 'a'.charCodeAt(0));
}
return mask;
}
words.forEach(word => {
const bitmaskKey = computeBitMask(word);
if (!anagramGroups.has(bitmaskKey)) {
anagramGroups.set(bitmaskKey, []);
}
anagramGroups.get(bitmaskKey).push(word);
});
return Array.from(anagramGroups.values());
}
const array1 = ["eat","tea","tan","ate","nat","bat"];
groupAnagramsBitMasking(array1); //output: [["eat","tea","ate"],["tan","nat"],["bat"]]
const array2 = [""];
groupAnagramsBitMasking(array2); //output: [[""]]
const array3 = ["a"];
groupAnagramsBitMasking(array3); //output: [["a"]]
Solution 5: Canonical Form Approach
function groupAnagramsCanonical(words) {
const anagramGroups = new Map();
words.forEach(word => {
const canonicalForm = word.split('').sort().join('');
if (!anagramGroups.has(canonicalForm)) {
anagramGroups.set(canonicalForm, []);
}
anagramGroups.get(canonicalForm).push(word);
});
return Array.from(anagramGroups.values());
}
const array1 = ["eat","tea","tan","ate","nat","bat"];
groupAnagramsCanonical(array1); //output: [["eat","tea","ate"],["tan","nat"],["bat"]]
const array2 = [""];
groupAnagramsCanonical(array2); //output: [[""]]
const array3 = ["a"];
groupAnagramsCanonical(array3); //output: [["a"]]
Solution 6: Sorted Tuple Key Approach
function groupAnagramsTupleKey(words) {
const anagramGroups = new Map();
words.forEach(word => {
const sortedTuple = [...word].sort().join('');
if (!anagramGroups.has(sortedTuple)) {
anagramGroups.set(sortedTuple, []);
}
anagramGroups.get(sortedTuple).push(word);
});
return Array.from(anagramGroups.values());
}
const array1 = ["eat","tea","tan","ate","nat","bat"];
groupAnagramsTupleKey(array1); //output: [["eat","tea","ate"],["tan","nat"],["bat"]]
const array2 = [""];
groupAnagramsTupleKey(array2); //output: [[""]]
const array3 = ["a"];
groupAnagramsTupleKey(array3); //output: [["a"]]
Solution 7: Regular Expression Approach
function groupAnagramsRegex(words) {
const anagramGroups = new Map();
function generateKey(word) {
return word.split('').sort().join('');
}
words.forEach(word => {
const key = generateKey(word);
if (!anagramGroups.has(key)) {
anagramGroups.set(key, []);
}
anagramGroups.get(key).push(word);
});
return Array.from(anagramGroups.values());
}
const array1 = ["eat","tea","tan","ate","nat","bat"];
groupAnagramsRegex(array1); //output: [["eat","tea","ate"],["tan","nat"],["bat"]]
const array2 = [""];
groupAnagramsRegex(array2); //output: [[""]]
const array3 = ["a"];
groupAnagramsRegex(array3); //output: [["a"]]