49

49. Group Anagrams (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 <= 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:

• Valid Anagram (Easy)
• Group Shifted Strings (Medium)

Solution 1.

// 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;
    }
};