Group all Anagrams together in C++
In this tutorial, we are going to learn to group all the anagrams together in a given vector of strings with C++. For instance, the given vector of strings is
[“rams”,”mars”,”silent”,”listen”,”cars”,”scar”] , then we have to group all anagrams together and return a two dimensional vector.[[“rams”,”mars”],[“silent”,”listen”],[“cars”,”scar”]].To implement this we will use unordered maps and two dimensional vectors.
Approach :
- Iterate over the given vector of string and for each string first sort it.
- Check whether the given sorted sequence is present in the unordered map or not.
- If the sorted sequence is not present then make it a key in the unordered map.
- If the sorted sequence is present then append the original string to the corresponding sorted sequence.
Finally, store all the values in a two-dimensional vector according to the key in the unordered map.
C++ implementation to group all anagrams together
Below is our C++ code to perform the task:
#include<bits/stdc++.h> using namespace std; vector<vector<string>> group(vector<string>& str) { vector<vector<string> > vec; unordered_map<string,vector<string> > m; for(int i=0;i<str.size();i++){ string x=str[i]; sort(x.begin(),x.end()); m[x].push_back(str[i]); } for(auto i:m){ vec.push_back(i.second); } return vec; } int main() { vector<string> str ={"ram","mar","listen","silent","lentsi","more","like"}; vector<vector<string>> ans; ans=group(str); cout<<"The grouped anagrams are as follows:"<<endl; for (int i = 0; i <ans.size(); i++) { for (int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << " "; cout << endl; } }
Output:
After running our program, we will able to get the result given below:
The grouped anagrams are as follows: like more ram mar listen silent lentsi
So from the output, we can see that we did it successfully.
Leave a Reply