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 <= 104
0 <= strs[i].length <= 100
strs[i]
consists of lower-case English letters.
Companies:
Amazon, Microsoft, Goldman Sachs, eBay, Apple, BlackRock, Facebook, Paypal, Uber, Yandex, Salesforce, Walmart Labs, Twilio, Two Sigma, Google, VMware, Snapchat, Splunk, Atlassian, Citadel
Related Topics:
Hash Table, String, Sorting
Similar Questions:
// OJ: https://leetcode.com/problems/group-anagrams/
// Author: github.com/lzl124631x
// Time: O(NWlogW)
// Space: O(NW)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& A) {
unordered_map<string, vector<string>> m;
for (auto &s : A) {
auto key = s;
sort(begin(key), end(key));
m[key].push_back(s);
}
vector<vector<string>> ans;
for (auto &[key, strs] : m) ans.push_back(strs);
return ans;
}
};
Or
// OJ: https://leetcode.com/problems/group-anagrams/
// Author: github.com/lzl124631x
// Time: O(NWlogW)
// Space: O(N)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& A) {
unordered_map<string, int> m;
vector<vector<string>> ans;
for (auto &s : A) {
auto key = s;
sort(begin(key), end(key));
if (!m.count(key)) {
m[key] = ans.size();
ans.emplace_back();
}
ans[m[key]].push_back(s);
}
return ans;
}
};