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(vector<string> &strs) {
vector<vector<string>> anagrams;
anagrams.reserve(strs.size());
unordered_map<array<int, 26>, int, array_hash> count_index;
for (const string &str : strs) {
array<int, 26> letter_count{};
for (char letter : str) {
++letter_count[index(letter)];
}
auto iter = count_index.find(letter_count);
if (iter == count_index.end()) {
count_index.emplace(letter_count, anagrams.size());
anagrams.emplace_back();
anagrams.back().push_back(str);
} else {
anagrams[iter->second].emplace_back(str);
}
}
return anagrams;
}
private:
struct array_hash {
size_t operator()(const array<int, 26> &count) const {
size_t key = 0;
for (int x : count) {
key ^= hash<int>{}(x) + 0x9e3779b97f4a7c15ULL + (key << 6) + (key >> 2);
}
return key;
}
};
static int index(char letter) {
return letter - 'a';
}
};