LeetCode Q49: Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

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

Use sort and hash. The key used in hash is in format C1X1C2X2... where C is a character, X is the number of C showing up in the string.

	class Solution {
	public:
	vector<vector<string> > groupAnagrams(vector<string>& strs){
	vector<vector<string> > r;
	unordered_map<string, int> myMap;
	unordered_map<string, int>::const_iterator itr;
	sort(strs.begin(), strs.end());
	for(int i=0; i<strs.size(); ++i){
	string s = strs[i];
	vector<int> f(26, 0);
	for(int j=0; j<s.length(); ++j){
	char c=s[j];
	f[c-'a']++;
	}
	string m="";
	for(int j=0; j<f.size(); ++j){
	if(f[j]!=0){
	char c='a'+j;
	m=m+string(1, c)+to_string(f[j]);
	}
	}
	itr=myMap.find(m);
	if(itr!=myMap.end()){
	int id=itr->second;
	r[id].push_back(s);
	}else{
	vector<string> ng;
	ng.push_back(s);
	r.push_back(ng);
	myMap[m]=r.size()-1;
	}
	}
	return r;
	}
	};

view raw Q49GroupAngrams.cpp hosted with ❤ by GitHub