力扣每日一题49：字母异位词分组

题目描述：

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

通过次数

542.1K

提交次数

799.9K

通过率

67.8%

思路和题解：

字母异位词里面的的字母都是相同的，只是排列顺序不同，如果我们把每个单词都排序一遍，排序后字母异位词是相等的，然后再将字符串数组排序一边，此时字母异位词就挨在一起了，我们只要把连在一起并且排序后相等的两个字母放进一个组合里，最后把所有的组合返回即可。听不懂的话我举个例子，就拿样例一来说strs=["eat","tea","tan","ate","nat","bat"],把每个单词排序得到a=[aet, aet ,ant ,aet ,ant ,abt],再将字符串数组a排序，排序的时候连带strs一起交换得到strs=[bat tea ate eat nat tan]   a=[abt aet aet aet ant ant] ，即

第一次将每个单词排序
strs=[eat tea tan ate nat bat] a=[aet aet ant aet ant abt] 
第二次将a中单词作为一个整体排序
strs=[bat tea ate eat nat tan] a=[abt aet aet aet ant ant] 

来看我的代码：

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> ans;vector<string> a;int n=strs.size();for(int i=0;i<n;i++){//先对原始字符串数组中每一个字符串进行排序a.push_back(strs[i]);sort(a[i].begin(),a[i].end());}// //test1// for(int i=0;i<n;i++)//     cout<<strs[i]<<" ";// cout<<endl;// for(int i=0;i<n;i++)//     cout<<a[i]<<" ";// cout<<endl;// 再对字符串数组a排序,strs跟着换for(int i=0;i<n-1;i++){int k=i;for(int j=i+1;j<n;j++){if(a[j]<a[k]) k=j;}string temp=a[i];a[i]=a[k],a[k]=temp;temp=strs[i],strs[i]=strs[k],strs[k]=temp;}// //test2// for(int i=0;i<n;i++)//     cout<<strs[i]<<" ";// cout<<endl;// for(int i=0;i<n;i++)//     cout<<a[i]<<" ";// cout<<endl;//这个时候字母异位词就黏在一起了int pos=0,i=0;while(pos<n){vector<string> group;group.emplace_back(strs[pos]);while(pos<n-1&&a[pos]==a[pos+1]){pos++;group.emplace_back(strs[pos]);}pos++;ans.emplace_back(group);}return ans;}
};

改进：

上述方法的核心是将所有的字母异位词放在一起（指位置相邻），然后再将相邻且排序后相等的字符串放在一个字符串数组里。其实将排序后的一个string作为键，对应的排序之前的string作为值放入一个map里，我们就可以直接把所有的字母异位词放在一起（不仅仅是字母异位词不是相邻，而且非字母异位词之前也分开了）。看代码：

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> ans;map<string,vector<string>> mp;int n=strs.size();for(int i=0;i<n;i++){string key=strs[i];sort(key.begin(),key.end());mp[key].emplace_back(strs[i]);}for(auto it=mp.begin();it!=mp.end();it++){ans.emplace_back(it->second);}return ans;}
};

运行：