Group Anagrams in C++

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"]

Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

• All inputs will be in lowercase.
• The order of your output does not matter.

This problem can be solved easily using Maps.
Solution involves 2 steps:

1. Sort the element and make it as the key.
2. Take the value and place it in the key.

In out example:

Pass 1:
Sort (eat) = aet
Our Map will be:
aet => eat

Pass 2:
Sort (tea) = aet
Our Map will be:
aet => eat, tea

Pass 3:
Sort (tan) = ant
Our Map will be:
aet => eat, tea
ant => tan

Pass 4:
Sort (ate) = aet
Our Map will be:
aet => eat, tea, ate
ant => tan

Pass 5:
Sort (nat) = ant
Our Map will be:
aet => eat, tea, ate
ant => tan, nat

Pass 6:
Sort (bat) = abt
Our Map will be:
aet => eat, tea, ate
ant => tan, nat
abt => bat

Finally we copy the values from each key and store it in 2D vector.
We are using C++, hence we need to use “unordered_map”. In which the first field will hold the key and the second field is a vector to hold multiple values.

Solution in C++

/*
* File     : group_anagrams.cpp
* Author   : ajay.thousand@gmail.com
* Copyright: @ prodevelopertutorial.com
*/

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

vector<vector<string> > groupAnagrams(vector<string>& input_set) 
{
    // the first value will hold the key, the second vector is used to hold the multiple values.
	unordered_map<string, vector<string> > my_map;
	vector<vector<string> > final_set;

	for (int i = 0; i < input_set.size(); i++)
	{
        // take value at the index as a key
		string key = input_set[i];

        //sort the key
		sort(key.begin(), key.end());

        // add the value to that key
		my_map[key].push_back(input_set[i]);

	}

	for (auto n : my_map)
	{
        // add all the values in the map to the final set
		final_set.push_back(n.second);
	}

	return final_set;
}

int main()
{
    vector<string> input_set;
    input_set.push_back("eat");
    input_set.push_back("tea");
    input_set.push_back("tan");
    input_set.push_back("ate");
    input_set.push_back("nat");
    input_set.push_back("bat");
    
    vector<vector<string> > final_set =  groupAnagrams(input_set);

    // print the output
    for (int i = 0; i < final_set.size(); i++)
    {
        if (final_set[i].size() > 0)
        {
            cout << " ( ";
            for (int j = 0; j < final_set[i].size(); j++)
                cout << final_set[i][j] << " ";
            cout << ")";
        }
        cout<<endl;
    }

	return 0;
}