4. Group Anagrams

#leetcode/49

Problem 🔗

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.

Solution

Solution in C++ using sort

We iterate over each word, that we call str, in the input vector strs. Next, we sort the characters in str using the sort() function, and we save them in sortedStr. Finally, we insert sortedStr as the key into the hashmap using map[sortedStr], and we push the original word (str) into the vector associated with that key using map[sortedStr].push_back(str).
In the end, we iterate through each key-value pair in the map and, for each pair, we push the vector of anagrams (val.second) into the res vector.

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> map;
    vector<vector<string>> res;
    
    for(string str : strs) {
        string sortedStr = str;
        sort(sortedStr.begin(), sortedStr.end());
        map[sortedStr].push_back(str);
    }
    
    for(auto val : map)
        res.push_back(val.second);

    return res;
}

• Time complexity: $O(n\cdot m\log m)$ (where n is the size of the vector, m is the size of the longest string; n for iterating over the whole vector, $m\log m$ for sorting chars in each string)
• Space complexity: $O(n\cdot m)$ (we are storing all the input)

Solution in C++ using counting sort

Since the input consists of lowercase English letters (26), we can use the counting sort algorithm. In fact, since its time complexity is $O(n+k)$ (where $k$ is the range of input, in our case 26), we can lower the time complexity of the sort algorithm from $O(m\log m)$ to $O(m+26)=O(m)$. Here I adapted the algorithm to our problem.

vector<vector<string>> groupAnagrams(vector<string>& strs) {
	unordered_map<string, vector<string>> map;
	vector<vector<string>> res;

	for(string str : strs) {
		string sortedStr = countSort(str);
		map[sortedStr].push_back(str);
	}

	for(auto val : map) {
		res.push_back(val.second);
	}

	return res;
}

string countSort(string& str) {        
    string sortedStr = str;
    array<int, 26> count = {};
    
    for (char c : str)
        count[c - 'a']++;
        
    int index = 0;
    for (int i = 0; i < 26; i++) {
        while (count[i] > 0) {
            sortedStr[index++] = 'a' + i;
            count[i]--;
        }
    }
    return sortedStr;
}

• Time complexity: $O(n\cdot m)$ (where n is the size of the vector, m is the size of the longest string)
• Space complexity: $O(n\cdot m)$ (we are storing all the input)