Group Anagrams
Problem
Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
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.
["bake", "beak", "rats", "star", "tea"][["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;
}Explanation
Two words are anagrams when they contain exactly the same letters in any order. So we need a signature that is identical for anagrams but different otherwise. Sorting a word's letters gives us exactly that.
For each word we compute key = "".join(sorted(w)) and use it as a hash map key. Every word that sorts to the same key gets appended into the same bucket (a list), so anagrams naturally pile up together.
Why does sorting work? Because rearranging letters cannot change their sorted order — "bake" and "beak" both sort to "abek", so they share a key.
Example: ["bake", "beak", "rats", "star", "tea"]. Keys are abek, abek, arst, arst, aet. The buckets become [bake, beak], [rats, star], and [tea].
At the end we just return all the bucket lists. The answer can be in any order, so the map's iteration order is fine.