Group Anagrams Together
Problem
Given a list of words, group those that are anagrams of each other (same multiset of letters). Return the groups in any order.
Two words are anagrams iff their characters sorted produce the same string. Hash every word by that sorted signature; words with the same signature land in the same bucket.
Input
["bake", "beak", "rats", "star", "tea"]Output
[["bake", "beak"], ["rats", "star"], ["tea"]]def group_anagrams(words):
buckets = {}
for w in words:
key = "".join(sorted(w))
buckets.setdefault(key, []).append(w)
return list(buckets.values())function groupAnagrams(words) {
const buckets = new Map();
for (const w of words) {
const key = w.split("").sort().join("");
if (!buckets.has(key)) buckets.set(key, []);
buckets.get(key).push(w);
}
return Array.from(buckets.values());
}class Solution {
public List<List<String>> groupAnagrams(String[] words) {
Map<String, List<String>> buckets = new HashMap<>();
for (String w : words) {
char[] chars = w.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
}
return new ArrayList<>(buckets.values());
}
}vector<vector<string>> groupAnagrams(vector<string>& words) {
unordered_map<string, vector<string>> buckets;
for (auto& w : words) {
string key = w;
sort(key.begin(), key.end());
buckets[key].push_back(w);
}
vector<vector<string>> out;
for (auto& kv : buckets) out.push_back(kv.second);
return out;
}