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