[力扣 Hot100]找到字符串中所有字母异位词

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

出处

思路

跟昨天的思路类似，也是两个指针构成滑动窗口，窗口大小固定为p的长度。将p的字符存到map中作为key，value为其出现的次数。对s进行遍历，窗口内若出现p中字符，对应的value–，若出现非p中字符，窗口滑动到非p中字符之后。窗口内字符检查完后若map中value均为0，窗口左侧索引即为一个候选结果。
实测用map会超时，最后用了定长26的vector。

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m=s.length();
        int n=p.length();
        vector<int> ans,t(26,0),tt(26,0);
        int i;
        for(i=0; i<n; i++){
            t[p[i]-'a']++;//计数
        }
        for(i=0;i<26;i++){
            if(t[i]==0){
                t[i]=-30001;
            }
        }
        int index=0;
        bool flag;
        while (index<=m-n)
        {
            flag=false;
            tt=t;
            i=index;
            for(; i<index+n; i++){
                if(tt[s[i]-'a']!=-30001)
                    tt[s[i]-'a']--;
                else{
                    flag=true; 
                    break;
                }
            }
            if(flag)
                index=i+1;
            else{
                for(auto item:tt){
                    if(item!=0&&item!=-30001)
                        flag=true;//这里顺便用一下flag，为方便理解也可以新定义一个
                }
                if(!flag)//如果全减到了0
                    ans.emplace_back(index);
                index++;
            }
        }  
    return ans;
    }
};
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
45