49. Group Anagrams
1. Description
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
2. Example
Example 1
Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]
Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
Explanation:
- There is no string in strs that can be rearranged to form “bat”.
- The strings “nat” and “tan” are anagrams as they can be rearranged to form each other.
- The strings “ate”, “eat”, and “tea” are anagrams as they can be rearranged to form each other.
Example 2
Input: strs = [""]
Output: [[""]]
Example 3
Input: strs = [“a”]
Output: [[“a”]]
3. Constraints
- 1 <= strs.length <= 10$^{4}$
- 0 <= strs[i].length <= 100
- strs[i] consists of lower-case English letters.
4. Solutions
Hash Table
n = strs.size(), k is the string size in strs
Time complexity : O(nk)
Space complexity : O(nk)
class Solution {
public:
vector<vector<string>> groupAnagrams(const vector<string> &strs) {
const int n = strs.size();
unordered_map<array<int, 26>, vector<string>, array_hash> anagrams;
for (const string &str : strs) {
array<int, 26> count{};
for (char c : str) {
++count[c - 'a'];
}
anagrams[count].emplace_back(str);
}
vector<vector<string>> groups;
for (auto &[count, group] : anagrams) {
groups.push_back(move(group));
}
return groups;
}
private:
struct array_hash {
size_t operator()(const array<int, 26> &a) const {
size_t h = 0;
for (int x : a) {
h ^= hash<int>{}(x) + 0x9e3779b9 + (h << 6) + (h >> 2);
}
return h;
}
};
};