Leetcode力扣解题记录--第49题（map）

题目链接：49. 字母异位词分组 - 力扣（LeetCode）

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

• 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
• 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
• 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

 题目作答

 解题的第一步是要找到一个对应关系，要将具有相同字母的放入到一个集合里，然后就可以根据这个集合的名字再取出集合里面的元素，也就是有相同字母但是不同序的单词。

利用map可以很好的找到对应关系，key就是具有相同字母的组合，map.second就是存放所有相同字母但是不同序的单词。

我们可以使用一个哈希表（ std::unordered_map），其中：

Key 是每个字符串排序后的结果。

Value 是一个字符串列表（vector<string>），用来存放所有能生成这个键的原始字符串。

Key：我们需要为每个字符串生成一个唯一的标识，这个标识对于所有字母异位词来说都应该是相同的。一个非常直观有效的方法是对字符串的字符进行排序。无论原始顺序如何，"eat", "tea", "ate" 在排序后都会得到同一个字符串："aet"。同样，"tan" 和 "nat" 排序后都会得到 "ant"。这个排序后的字符串 "aet" 或 "ant" 就可以作为它们共同的“键”。

vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> map;for (string str : strs) {string key = str;sort(key.begin(), key.end());// 使用排序后的 `key` 作为哈希表的键，// 将原始的、未排序的字符串 `str` 添加到该键对应的值中。map[key].push_back(str);}// 存放返回结果vector<vector<string>> result;for (auto pair : map) {// pair.first 是键// pair.second 是值（如 ["eat", "tea", "ate"]）result.push_back(pair.second);}return result;}