成都建站模板,网站开发程序,微信商城和微网站,四川网站备案核验单题目描述#xff1a;
给你一个字符串数组#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1:
输入: strs [eat, tea, tan, ate
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1:
输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]
示例 2:
输入: strs []
输出: [[]]示例 3:
输入: strs [a]
输出: [[a]] 提示
1 strs.length 1040 strs[i].length 100strs[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:vectorvectorstring groupAnagrams(vectorstring strs) {vectorvectorstring ans;vectorstring a;int nstrs.size();for(int i0;in;i){//先对原始字符串数组中每一个字符串进行排序a.push_back(strs[i]);sort(a[i].begin(),a[i].end());}// //test1// for(int i0;in;i)// coutstrs[i] ;// coutendl;// for(int i0;in;i)// couta[i] ;// coutendl;// 再对字符串数组a排序,strs跟着换for(int i0;in-1;i){int ki;for(int ji1;jn;j){if(a[j]a[k]) kj;}string tempa[i];a[i]a[k],a[k]temp;tempstrs[i],strs[i]strs[k],strs[k]temp;}// //test2// for(int i0;in;i)// coutstrs[i] ;// coutendl;// for(int i0;in;i)// couta[i] ;// coutendl;//这个时候字母异位词就黏在一起了int pos0,i0;while(posn){vectorstring group;group.emplace_back(strs[pos]);while(posn-1a[pos]a[pos1]){pos;group.emplace_back(strs[pos]);}pos;ans.emplace_back(group);}return ans;}
};
改进
上述方法的核心是将所有的字母异位词放在一起指位置相邻然后再将相邻且排序后相等的字符串放在一个字符串数组里。其实将排序后的一个string作为键对应的排序之前的string作为值放入一个map里我们就可以直接把所有的字母异位词放在一起不仅仅是字母异位词不是相邻而且非字母异位词之前也分开了。看代码
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {vectorvectorstring ans;mapstring,vectorstring mp;int nstrs.size();for(int i0;in;i){string keystrs[i];sort(key.begin(),key.end());mp[key].emplace_back(strs[i]);}for(auto itmp.begin();it!mp.end();it){ans.emplace_back(it-second);}return ans;}
};
运行
