Medium
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.
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"]]
Constraints:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
/*
Given array of strings, group anagrams together (same letters diff order)
Ex. strs = ["eat","tea","tan","ate","nat","bat"] -> [["bat"],["nat","tan"],["ate","eat","tea"]]
Count chars, for each string use total char counts (naturally sorted) as key
Time: O(n x l) -> n = length of strs, l = max length of a string in strs
Space: O(n x l)
*/
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> m;
for (int i = 0; i < strs.size(); i++) {
string key = getKey(strs[i]);
m[key].push_back(strs[i]);
}
vector<vector<string>> result;
for (auto it = m.begin(); it != m.end(); it++) {
result.push_back(it->second);
}
return result;
}
private:
string getKey(string str) {
vector<int> count(26);
for (int j = 0; j < str.size(); j++) {
count[str[j] - 'a']++;
}
string key = "";
for (int i = 0; i < 26; i++) {
key.append(to_string(count[i] + 'a'));
}
return key;
}
};
No comments:
Post a Comment