Anagram Cluster Formation — Problem Statement & Solution Guide
Problem Description
Given an array of strings, group the anagrams together and return each group.
Examples
Input
["eat","tea","tan","nat","bat"]
Output
[["eat","tea"],["tan","nat"],["bat"]]
Explanation: Step-by-step: First, we sort each string in the input array. Then, we group the strings by their sorted values. Finally, we return the groups of anagrams.
Input
["cat","tac","dog","god"]
Output
[["cat","tac"],["dog","god"]]
Explanation: Step-by-step: First, we sort each string in the input array. Then, we group the strings by their sorted values. Finally, we return the groups of anagrams.
Constraints
- 1 <= n <= 10^4
- Strings consist of lowercase English letters.
Optimal Approach & Strategy
Use a HashMap where the key is the sorted string and the value is a list of original strings. Iterate, sort each string, group by key. Time O(N * K log K), Space O(N * K).
Brute Force Approach
Compare every string with every other string. Time O(N^2 * K).
Verified Code Solutions
function groupAnagrams(strs) {
const anagrams = {};
for (const str of strs) {
const sortedStr = str.split('').sort().join('');
if (!anagrams[sortedStr]) anagrams[sortedStr] = [];
anagrams[sortedStr].push(str);
}
return Object.values(anagrams);
}class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> anagrams;
for (const string& str : strs) {
string sortedStr = str;
sort(sortedStr.begin(), sortedStr.end());
if (anagrams.find(sortedStr) == anagrams.end()) anagrams[sortedStr] = {};
anagrams[sortedStr].push_back(str);
}
vector<vector<string>> result;
for (const auto& pair : anagrams) result.push_back(pair.second);
return result;
}
}class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> anagrams = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String sortedStr = new String(chars);
if (!anagrams.containsKey(sortedStr)) anagrams.put(sortedStr, new ArrayList<>());
anagrams.get(sortedStr).add(str);
}
return new ArrayList<>(anagrams.values());
}
}def group_anagrams(strs):
anagrams = {}
for str in strs:
sorted_str = ''.join(sorted(str))
if sorted_str not in anagrams:
anagrams[sorted_str] = []
anagrams[sorted_str].append(str)
return list(anagrams.values())function groupAnagrams(strs) {
const anagrams = {};
for (const str of strs) {
const sortedStr = str.split('').sort().join('');
if (!anagrams[sortedStr]) anagrams[sortedStr] = [];
anagrams[sortedStr].push(str);
}
return Object.values(anagrams);
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.