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

发布时间:2024年01月19日

题目描述

给定两个字符串 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;
    }
};
文章来源:https://blog.csdn.net/qq_53627591/article/details/135689025
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。