LeetCode 热题100——49.字母异位词分组

题目：

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

示例 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"]]

提示：

• 1 <= strs.length <= 10^4

• 0 <= strs[i].length <= 100

• strs[i]仅包含小写字母

题解：

核心要点：

两个字符串是字母异位词，当且仅当它们排序后的结果完全相同。例如 "eat" 和 "tea" 排序后都是 "aet"。

算法步骤：

1.创建一个哈希表 unordered_map<string, vector<string>> mp，键为排序后的字符串，值为原始字符串的列表。

2.遍历输入数组中的每个字符串 str：

3.复制一份到 key，并对 key 进行排序。

4.将原始字符串 str 加入到 mp[key] 对应的列表中。

5.遍历哈希表，将每个 vector<string>（即一组字母异位词）加入到结果 ans 中。

6.返回 ans。

答案：

class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string,vector<string>> mp; for(auto str:strs){ string key=str; sort(key.begin(),key.end());//排序后得到键 mp[key].push_back(str);//将原始字符串加入对应组 } vector<vector<string>> ans; for(auto it=mp.begin();it!=mp.end();it++){ ans.push_back(it->second); } return ans; } };