21 . 字母异位词分组

题目介绍

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

提示：

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

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

全文核心1400字，阅读+思考8min

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

解析

1 . 本题需求很明确：给你一个字符串数组。对于其中相同字母（排列组合）组合成的字符串归为一组。

2 . 很自然的，结果要求返回一个二维数组。不难想，其元素则是，一组一组“字母异位词”

3 . 初拿到此题，不由想：难道我们要通过递归每个字符串，去得出每个字符串的各种排列组合……

4 . 再去统计哪些组合出现，再整合

5 . 未免想复杂了，这只是个分类工作

哈希

1 . 你可能会好奇，怎么就突然用上——“哈希”？请听接下来的分析

2 . 首先清楚此处的核心需求，材料都已经给你（vector<string>& strs）

3 . 我们需要做的，只是将它们分类，按照一定标准，把几个字符串分为一个数组。最后许多个数组合成一个大的数组

4 . 返回这个二维数组

5 . 而这个“一定标准”是什么呢？比如"nat"和"tan"凭什么分为一组，而“ate”、"eat"和"tea"凭什么分为一组

不难发现，它们都有相同的字母组成，一个不多一个不少——只是顺序不同

6 . 而让看起来顺序不一样的字母串归在一类，首先让它们展示出共性

for(auto & e : strs) { string key = e; sort(key.begin(),key.end()); // 对key原地排序，"nat"和"tan"，必然展示出共性—— "ant" }

7 . 既然有了分类标准，就应该开始分类

8 . 本题要求返回一个二维数组——“万丈高楼平地起”，必然先得把一维数组准备好

9 . 不如，让key作为一个指标，它对应映射一组由key排列组合的单词

10 . 结构：unordered_map<string,vector<string>>

class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { std::unordered_map<string,vector<string>> mp; for(auto & e: strs) { string key = e; sort(key.begin(),key.end()); mp[key].push_back(e);// 展现出共性后，把当前的e往key组塞 } } };

注：

字符串少拷贝，使用for(auto & e: strs)

11 . 现在mp已经有许多组 <key , vector<string>>

12 . 还记得要求返回二维数组吗？那么不难想到，最终结果集就是mp里的vector<string>组合起来成为的二维数组

13 . 那还等什么，遍历mp，把每一组的vector<string>作为元素放进ret数组里

vector<vector<string>> vv; for(auto & it:mp) // 这里的it 为 pair<string,vector<string>> { vv.push_back(it.second); }

完整代码：

class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { // 分类 std::unordered_map<string,vector<string>> mp; for(auto & e: strs) { string key = e; sort(key.begin(),key.end()); mp[key].push_back(e); } // 整合 vector<vector<string>> vv; for(auto & it:mp) { vv.push_back(it.second); } return vv; } };

总结以及完整参考代码

class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { // 分类 std::unordered_map<string,vector<string>> mp; for(auto & e: strs) { string key = e; sort(key.begin(),key.end()); mp[key].push_back(e); } // 整合 vector<vector<string>> vv; for(auto & it:mp) { vv.push_back(it.second); } return vv; } };