Group Anagrams (#49 Leetcode)

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 lowercase English letters.

 

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string s : strs) {
            mp[strSort(s)].push_back(s);
        }
                 
        vector<vector<string>> anagrams;
        for (auto& p : mp) { 
            //cout <<  p.first << " " << p.second << endl;
            anagrams.push_back(p.second);
            
        }
        return anagrams;
    }
private:
    string strSort(string s) {
        int counter[26] = {0};
        for (char c : s) {
            counter[c - 'a']++;
        }
        string t;
        for (int c = 0; c < 26; c++) {
            t += string(counter[c], c + 'a');
            //cout << string(counter[c], c + 'a') << endl;
            //cout << t << endl;
        }
        //cout << t << endl;
        return t;
    }
};

In the above line, string() object is constructed based on the n consecutive copies of characters c. Click here to read more. 

Here, string(size_t n, char c) is called fill constructor. It fills the string with n consecutive copies of character c.

Instead of strSort, we can just use sort(s) from algorithm library.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string s : strs) {
            mp[strSort(s)].push_back(s);
        }
             
        
        vector<vector<string>> anagrams;
        for (auto& p : mp) { 
            //cout <<  p.first << " " << p.second << endl;
            anagrams.push_back(p.second);
        
        }
        return anagrams;
    }
    
private:
    string strSort(string s) {
        sort(s.begin(), s.end());
        return s;
    }
};