49. Group Anagrams

题意：

给一组string，将所含字符相同的字符串分在一组。

思路1：暴力求解

把每个字符串拆成字符存在vector中，对其排序，用一个map把所含字符相同的字符串存在一个vector中。

vector<vector<string>> groupAnagrams(vector<string>& strs) {//52ms
	map<vector<char>, vector<string>> rm;
	vector<vector<string>> res;
	for (auto str : strs) {
		vector<char> temp;
		for (int i = 0; i < str.size(); ++i)
			temp.push_back(str[i]);
		sort(temp.begin(), temp.end());
		rm[temp].push_back(str);
	}
	for (auto vs : rm)
		res.push_back(vs.second);
	return res;
}

思路2：利用哈希

网上大佬的代码，使26个字母分别对应一个质数，这样同一组字符的乘积唯一，使乘积相同的字符串存在一起。

int prime[26] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };

vector<vector<string>> groupAnagrams(vector<string>& strs) {
	unordered_map<int, int> m;
	vector<vector<string>> res;
	for (auto str : strs) {
		int val = 1;
		for (int i = 0; i < str.size(); ++i)
			val *= prime[str[i] - 'a'];
		if (m.find(val) == m.end()) {//m中无val
			m[val] = res.size();
			res.push_back(vector<string>({ str }));
		}
		else
			res[m[val]].push_back(str);
	}
	return res;
}