🗺 438.找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
思路
基本思想
为了找出所有的字母异位词，需要从s的头部开始遍历，每次都取出p长度的子串，判断是不是字母异位词，代码很好写，但是第一版代码超时了
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
| class Solution {
public:
//滑动窗口中保持与p一样的大小
//进一个出一个，每个滑动窗口都判断是不是p的字母异位词
//由于会重复
vector<int> findAnagrams(string s, string p) {
//保存所有字母异位词的起始下标
vector<int> res;
if(s.size()<p.size())
return res;
//从头开始，看每一个子串是不是异位词
for(int i=0;i<=s.size()-p.size();++i){
if(isSame(s.substr(i,p.size()),p))
res.push_back(i);
}
return res;
}
//超时主要是这里判断字母异位词时
//判断是不是异位词
bool isSame(string str1,string str2){
unordered_map<char,int> umap;
for(auto c:str1){
umap[c]+=1;
}
for(auto c:str2){
if(umap[c]>0)
umap[c]-=1;
else
return false;
}
return true;
}
};
|
原因就是在字母异位词的判断每次都需要从头开始判断，所以防止超时的办法就是改进判断字母异位词的方法，可以看到，上一个子串和下一个子串之间只是删除了最左边的元素，最右边新来一个元素，中间的部分都是重复的，没有必要重复统计，并且判断字母异位词的办法有很多。排序之后看是否相等，字符数量是否相等都可以
这里采用统计字符数量的办法，这样中间的部分不用重复统计，只需要统计删除和新增的部分，并且p字符串只需要统计一次
执行流程
- 先统计出来p中元素的出现次数，同时将s中从0开始的子串截取出来，处理这个特殊情况
- 然后判断从0开始的子串与p是不是字母异位词
- 然后正常的进一个出一个，从而减少统计的开销
- 从当前位置进一个出一个，相当于当前的滑动窗口中是以i+1为起点的子串
代码
根据以上分析，得出以下代码：
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
| class Solution {
public:
//滑动窗口中保持与p一样的大小
//进一个出一个，每个滑动窗口都判断是不是p的字母异位词
vector<int> findAnagrams(string s, string p) {
//保存所有字母异位词的起始下标
vector<int> res;
if(s.size()<p.size())
return res;
//统计两个字符串出现的次数
vector<int> snum(26,0);
vector<int> pnum(26,0);
for(int i=0;i<p.size();++i){
pnum[p[i]-'a']+=1;
snum[s[i]-'a']+=1;
}
if(pnum==snum)
res.push_back(0);
//从头开始，看每一个子串是不是异位词
for(int i=0;i<s.size()-p.size();++i){
//删除左边的
snum[s[i]-'a']-=1;
//加入右边的
snum[s[i+p.size()]-'a']+=1;
//相当于以i+1为起点
if(snum==pnum)
res.push_back(i+1);
}
return res;
}
};
|
总结
第一版的代码其实没有问题，只是时间花销太大，第二版的代码只是改进了判断字母异位词的时间，整体的思路并没有变化，由于滑动窗口变化一步，其中的大部分元素其实没有变化，所以不需要重复统计
并且统计时需要注意细节，不要使得下标越界具体的细节就是删除当前元素，加入下一个新元素，相当于以i+1为起点，此时起点为0的子串需要单独处理