🐹 49.字母异位词分组
思路
基本思想
为了将所有的字母异位词分组，首先需要能判断两个单词是不是字母异位词，所以需要单独定义一个函数，如果两个单词是字母异位词，才能属于同一组
对于每一个单词，判断已有的结果容器中是不是有字母异位词，只需要将结果容器中每一组的第一个单词拿出来判断即可，因为这一组中全都是字母异位词，如果与第一个单词成为了字母异位词，那么这个单词就可以加入这一组
所以整体的流程就是，针对每一个单词，依次取出结果容器中每一组的第一个进行判断，找到了字母异位词就加入那一组，但是这样会超时，但是代码没错：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public:
//将所有的字母异位词保存在一起
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
//遍历给定的每一个单词，查看是否有已知的字母异位词
for(int i=0;i<strs.size();++i){
//从已有的结果列表中查看属于哪个字母异位词容器
int j=0;
for(;j<res.size();++j){
//找到了属于哪一个字母异位词容器，直接break准备插入
if(isSame(strs[i],res[j][0]))
break;
}
//区分是加入新的容器还是旧的容器
if(j==res.size()){
vector<string> temp;
temp.push_back(strs[i]);
res.push_back(temp);
}else{
res[j].push_back(strs[i]);
}
}
return res;
}
bool isSame(string str1,string str2){
if(str1.size()!=str2.size())
return false;
//将第一个字符串转换成一个字典用来查询
//不知道这样是不是可以
vector<int> num(26,0);
for(auto c:str1){
num[c-'a']+=1;
}
for(auto c:str2){
//还有对应的字符
if(num[c-'a']>0)
num[c-'a']-=1;
else
return false;
}
return true;
}
};
|
于是从上面的思路中，想办法简化时间复杂度，因为上面的内存循环主要是找到合适的字母异位词的小组，所以将内层循环进行改造
所有的字母异位词的小组都有一个标志，标志的得来是基于所有的字母异位词按照相同的排序规则排序之后变成同样的元素，例如ate和eta排序之后都变成了aet，所以定义了一个unordered_map用来存储小组和对应的标志之间的映射关系
此时对于每一个词来说，找到自己的字母异位词小组之前，需要先对自己进行排序，所以需要先转化成字符数组排序，再转换成字符串，一旦找到了自己对应的字母异位词小组，需要将其没有排序之前的值加入对应的小组，如果没有找到自己的字母异位词小组，说明这个单词需要自成一组
这样通过字典的方式查询到自己的字母异位词，而不是内层使用一个for循环从前到后的找到自己的字母异位词小组，从而达到减少时间复杂度的目的
执行流程
- 从前到后遍历每一个单词
- 对每一个单词先转化成字符数组排序，之后在转化成字符串试图找到自己的字母异位词小组
- 如果找到了，那么就将原值加入小组
- 如果没找到，那么原值自成一组
- 最后将字典中的所有字母异位词集中在一起返回
原值指的是没有经过排序之前的单词
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
//将所有的字母异位词保存在一起
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string,vector<string>> umap;
for(int i=0;i<strs.size();++i){
//将当前单词转化成字符数组再进行排序
vector<char> temp(strs[i].begin(),strs[i].end());
sort(temp.begin(),temp.end());
//排序之后重新进行查找，字母异位词排序之后变成了同一个单词
string str=string(temp.begin(),temp.end());
//找到了字母异位词的小组
if(umap.find(str)!=umap.end()){
vector<string> group=umap[str];
//新的字母异位词加入小组,加入时加入的是本身
group.push_back(strs[i]);
//小组更新
umap[str]=group;
}
//没找到字母异位词的小组，他就是新的小组
else{
vector<string> group;
//新的字母异位词加入小组
group.push_back(strs[i]);
//小组更新
umap[str]=group;
}
}
//遍历完成之后，将所有的字母异位词小组加入结果容器
for(auto it=umap.begin();it!=umap.end();++it){
res.push_back(it->second);
}
return res;
}
};
|
总结
主要是如何找到自己的字母异位词小组，字母异位词排序之后变成相同的词，这个思想很重要