题目
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
思路
由于本题是要将所用字母相同的字符串归类，因此可以将每个字符串进行排序，排序结果相同的即为同一类；将排序后的结果作为键值KEY存成一个map形式，其对应的原始字符串用set存进该键值处。
每个键值对应一组字母异位词，然后将这些提取出来存至result中
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
vector<vector<string>> result;
unordered_map<string, multiset<string>> hashNum;
for(auto eve : strs)
{
auto temp = eve;
sort(temp.begin(), temp.end());
hashNum[temp].insert(eve);
}
for (auto num : hashNum)
{
vector<string> strss(num.second.begin(), num.second.end());
result.push_back(strss);
}
return result;
}
};
int main(int argc, char* argv[])
{
vector<string> strs = { "eat", "tea", "tan", "ate", "nat", "bat" };
auto res = Solution().groupAnagrams(strs);
return 0;
}
对字符串进行内部排序的方法：
string sortStr(string s)
{
vector<int>count(26, 0);
for (int i = 0; i < s.size(); ++i)
{
++count[s[i] - 'a'];
}
string str;
for (int i = 0; i < 26; ++i)
{
if(count[i])
{
str += ('a' + i);
}
}
return str;
}
lsstcode高亮代码
class Solution3 {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ret_vect;
unordered_map<string, int> record;
string DNA;
int num = 0;
for (int i = 0; i<strs.size(); i++) {
DNA = strs[i];
sort(DNA.begin(), DNA.end());
//如果一个字符串的异位词没出现过，就给record进行编码，record中储存了排序后的不同结果及，对应的int值递增
if (record.find(DNA) == record.end()) {
record[DNA] = ++num;
ret_vect.push_back(vector<string>(1, strs[i]));
}
//如果一个字符串的异位词出现过，那马在record中找到它的位置，在结果中对应的位置插入这个字符串（ret_vect的KEY是从0开始，record是从1开始，所以需要-1）
else
ret_vect[record[DNA] - 1].push_back(strs[i]);
}
return ret_vect;
}
};
