LeetCode49——Group Anagrams 青旅半醒 2022-08-09 12:41 105阅读 0赞 LeetCode49——Group Anagrams 题意: 给定一组string,将这些string分类,同一类string满足如下条件: 1.在同类内部,按照字典序排列。 2.不同类的string所包含的字母不一样。 那么思路就是,首先区分,然后排序。 要做到区分很简单,首先对于不同类来说,他们包含的字母肯定不一样,那么将每个string进行排序(sort方法即可),就实现了string的区分,这里我们需要构造一个map来实现。 又如何对加入同一类别的子串进行字典序排列呢? 这里我们用到了STL中一个重要的容器multiset(注意不能使用set,具体在代码注释中说明)。 回顾一下set的特性:所有元素都会根据元素的键值自动被排序,set里面的元素键值(key)就是实值(value),set不允许有两个相同的key,所以此处我们使用multiset。 红黑树是一种平衡二叉树,自动排序效果很不错,所以set采用了红黑树为底层机制。 回到题目,基于上述理论,我们很容易想到,用set就可以完成同一类别string的字典序排列了。 因此,我们构建如下数据结构: map <string , multiset<string> >myMap; 代码如下: class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { map<string, multiset<string>>myMap;//用set不行,需要用multiset vector< vector<string> >result; for (int i = 0; i < strs.size(); i++) { string temp = strs[i]; sort(temp.begin(), temp.end()); myMap[temp].insert(strs[i]); }//构建map auto it = myMap.begin(); while (it != myMap.end()) { vector<string>temp(it->second.begin(), it->second.end()); result.push_back(temp); ++it; } return result; } };
还没有评论,来说两句吧...