每日OJ题_哈希表⑤_力扣49. 字母异位词分组

目录

力扣49. 字母异位词分组

解析代码

---

力扣49. 字母异位词分组

49. 字母异位词分组

难度 中等

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {}
};

---

解析代码

        互为字母异位词的单词有⼀个特点：将它们排序之后，两个单词应该是完全相同的。 所以可以利用这个特性，将单词按照字典序排序，如果排序后的单词相同的话，就划分到同一组中。

        这时我们就要处理两个问题：

• 排序后的单词与原单词需要能互相映射
• 将排序后相同的单词划分到同⼀组

利用语言提供的容器的强大的功能就能实现这两点：

• 将排序后的字符串（ string ）当做哈希表的 key 值
• 将字母异位词数组（ vector<string> ）当成 val 值。

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>> hash;for(auto& e : strs){string tmp = e;sort(tmp.begin(), tmp.end()); // 排序后异位次的key值都相等了hash[tmp].push_back(e);}vector<vector<string>> ret;for(auto& [x, y] : hash) // 范围for得到两个值的用法{ret.push_back(y);}return ret;}
};