Group anagrams in C++
Group anagrams in C++ is a common problem in programming interviews and competitions. Anagrams are words or phrases that are formed by rearranging the letters of another word or phrase, and group anagrams means grouping the anagrams of a list or words together. In this blog, we will discuss how to implement a solution for this problem in C++.
Problem Statement:
Given a list of strings, group the anagrams together. You can return the answer in any order.
For example, given the following list of strings:
["eat", "tea", "tan", "ate", "nat", "bat"]
Return:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Approach:
We can solve this problem by creating a hashmap (unordered_map in C++) where the key is the sorted string, and the value is a vector of strings that are anagrams of the key. We will loop through each string in the input list and sort it to use it as the key for the hashmap. After that, we will push the original string into the value vector of the corresponding key in the hashmap. Finally, we will loop through the hashmap and push the vectors into a result vector to return.
Syntax:
unordered_map<string, vector<string>>hashmap;
Code with output:
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<vector<string>>groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>>hashmap;
vector<vector<string>> result;
for (auto str : strs) {
string sorted_str = str;
sort(sorted_str.begin(), sorted_str.end());
hashmap[sorted_str].push_back(str);
}
for (auto&pair :hashmap) {
result.push_back(pair.second);
}
return result;
}
int main() {
vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
vector<vector<string>> result = groupAnagrams(strs);
for (auto group : result) {
cout<< "[ ";
for (auto str : group) {
cout<< str << " ";
}
cout<< "]" <<endl;
}
return 0;
}
Output:
[ bat ]
[ tan nat ]
[ eat tea ate ]
In the main function, we initialize the input list with the example strings and call the groupAnagrams function. After that, we loop through each group in the result vector and print it out surrounded by square brackets.
While the above solution is simple and efficient, it is important to note that the sorting of each string can be expensive, especially if the strings are long. A more optimized solution can be achieved by using character frequency maps as the key instead of sorting.
In this approach, we create a frequency map of each string where the key is a character and the value is the frequency of that character. After that, we utilize this frequency map as the key for the hashmap. We loop through each string in the input list, create its frequency map, and push the original string into the value vector of the corresponding key in the hashmap. Finally, we loop through the hashmap and push the value vectors into a result vector to return.
Syntax:
unordered_map<string, vector<string>>hashmap;
Code with output:
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<vector<string>>groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>>hashmap;
vector<vector<string>> result;
for (auto str : strs) {
string freq_map(26, '0');
for (auto c : str) {
freq_map[c - 'a']++;
}
hashmap[freq_map].push_back(str);
}
for (auto&pair :hashmap) {
result.push_back(pair.second);
}
return result;
}
int main() {
vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
vector<vector<string>> result = groupAnagrams(strs);
for (auto group : result) {
cout<< "[ ";
for (auto str : group) {
cout<< str << " ";
}
cout<< "]" <<endl;
}
return 0;
}
Output:
[ bat ]
[ tan nat ]
[ eat tea ate ]
In the main function, we initialize the input list with the example strings and call the groupAnagrams function. After that, we loop through each group in the result vector and print it out surrounded by square brackets.
Conclusion:
In this blog, we discussed how to group anagrams in C++ using a hashmap. We sorted each string in the input list to use as the key for the hashmap and pushed the original string into the value vector of the corresponding key. After that, we looped through the hashmap and pushed the value vectors into a result vector to return. This approach has a time complexity of O(NKlogK), where N is the number of strings in the input list and K is the maximum length of a string in the list.