49. Group Anagrams
1. Description
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.
2. Example
Example 1:
Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]
Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
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) {
unordered_map<array<int, 26>, vector<string>, _vector_hash> anagram_strings;
for (auto &str : strs) {
array<int, 26> letter_count = {};
for (auto letter : str) {
++letter_count[letter - 'a'];
}
anagram_strings[letter_count].emplace_back(str);
}
vector<vector<string>> group_anagrams;
for (auto &iter : anagram_strings) {
group_anagrams.emplace_back(move(iter.second));
}
return group_anagrams;
}
private:
struct _vector_hash {
size_t operator()(const array<int, 26> &letters) const {
size_t key = 0;
for (int i = 0; i < 26; ++i) {
key = key * 10 + letters[i];
}
return key;
}
};
};