49. 字母异位词分组 - 力扣（LeetCode）

自己的思路

<aside> 💡 主要根据两点：1、将string映射到长26的int数组（哈希），2、对int数组进行排序使异位词聚在一起

</aside>

自己的思路太繁杂了，大致以下几步：

1. 由于str全是小写字母，所以将每个str映射到一个长为26的数组
2. 以<str映射数组, str下标>的格式存入vector
3. 对vector进行排序，由于vector按第一个元素，即映射数组进行排序，所以异位词会聚在一起
4. 对比相邻元素，划分不同的异位词组，存入ans数组

代码

vector<vector<string>> groupAnagrams(vector<string>& strs) {
	if (strs.empty())
		return {};

	vector<vector<int>> count(strs.size(), vector<int>(26, 0));
	// 使用vector记录每个单词的哈希表及其下标
	vector<std::pair<vector<int>, int>> record;
	// 统计每个单词的哈希表
	for (int i = 0; i < strs.size(); ++i) {
		for (char c : strs[i]) {
			++count[i][c - 'a'];
		}
		record.push_back({ count[i], i });
	}
	// 排序使异位词聚在一起
	std::sort(record.begin(), record.end());

	// 排序后异位词一定相邻，所以只要对比相邻元素即可
	vector<vector<string>> ans;
	for (int i = 1; i <= record.size(); ++i) {
		ans.push_back({ strs[record[i - 1].second] });
		while (i < record.size() && record[i].first == record[i - 1].first) {
			ans.back().push_back(strs[record[i].second]);
			++i;
		}
	}
	return ans;
}

题解的思路

题解的思路中，异位词分组的任务在完善哈希表时完成

<aside> 💡 建立一个unordered_map，以排序后的str为key，异位词分组为value

</aside>

题解中还使用了emplace_back来简化了很多工作，可以学习

代码

vector<vector<string>> groupAnagrams(vector<string>& strs) {
	if (strs.empty())
		return {};

	// 以排序后的字符串为键，存储异位词数组
	unordered_map<string, vector<string>> mp;
	for (string str : strs) {
		string key = str;
		std::sort(key.begin(), key.end());
		// 使用emplace_back可以省去未找到时初始化空数组的工作
		mp[key].emplace_back(str);
	}
	// 将map中的所有元素转移到vector中
	vector<vector<string>> ans;
	for (auto it = mp.begin(); it != mp.end(); ++it) {
		// 使用emplace_back直接从map构造vector
		ans.emplace_back(it->second);
	}
	return ans;
}