group anagrams

###Anagram ? 🍡

two strings are anagram if and only if they are have the same length and same characters at same or different positions

example: "abc" is anagram "cba", "abcd" is not anagram of "cbad"

#####Problem specification: group the anagram by length,

in: { "mom", "omm", "good", "sam", "doog", "msb", "godo"}
out: { 
       {"mom", "omm"},
       {"good", "doog", "godo"},
       {"sam"},
       {"msb"}
    }

the idea is simple, we created a hashmap, key : sorted string, value : string id to the input list. we noticed the property of anagram, they are the same when two anagram are sorted, we can use it as key to the map; then multiple anagrams will hit the same bucket, we stored its array index expandably. Finally, iterate the map, to output the anagrams.

#include <unordered_map>
#include <iostream>
#include <vector>

using namespace std; 


/* why cannot do this simple questiom during the interview, I am so stupid  */
void groupAnagrams(const vector<string> in) 
{
	unordered_map<string, vector<int>> map; 

	for(int id = 0; id < in.size(); id++)
	{
		string str = in[id]; 
		sort(str.begin(), str.end()); 
		map[str].push_back(id); 
	}
	for(unordered_map<string, vector<int>>::iterator it = map.begin(); it != map.end(); it++ )
	{
		for( int i = 0; i < (it -> second).size(); i++ )
		{
			cout << in[ (it->second)[i] ] << " ,"; 
		}
		cout << endl; 
	}
}
 

int main()
{
	vector<string> in;  
	in.push_back("abc"); 
	in.push_back("cba"); 
	in.push_back("abd"); 

	groupAnagrams(in);


	return 0; 
}