Group Anagrams

MediumStrings

Group the strings that are anagrams of one another. Return the groups in any order.

Constraints

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters

Sorted string as key

Time O(n * k log k) where k is the max word lengthSpace O(n * k)

Two words are anagrams exactly when their sorted characters match. Use the sorted form (or a letter-count signature) as a hash-map key and append each word to its bucket.

#include <bits/stdc++.h>
using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        groups[key].push_back(s);
    }
    vector<vector<string>> res;
    for (auto& [_, v] : groups) res.push_back(move(v));
    return res;
}