题解 | #最小覆盖子串#

最小覆盖子串

https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

/*
	HW双指针3 最小覆盖子串

*/
class Solution {
public:
    unordered_map<char,int>hash;
    bool check()
    {
        for(auto it=hash.begin();it!=hash.end();it++){
            if(it->second<=0)return false;
        }
        return true;
    }

    string minWindow(string S, string T) {
        int lens=S.length(),lent=T.length();
        for(int i=0;i<lent;i++){
            if(hash.count(T[i]))hash[T[i]]--;
            else hash[T[i]]=0;
        }
        int lo=0,hi=0;
        int cnt=lens+1;
        int l=-1,r=-1;
        for(;hi<lens;hi++){
            char ch=S[hi];
            if(hash.count(ch))hash[ch]++;
            while(check()){
                if(cnt>hi-lo+1){
                    cnt=hi-lo+1;
                    l=lo;
                    r=hi;
                }
                char cl=S[lo];
                if(hash.count(cl)){
                    hash[cl]--;
                }
                lo++;
            }
        }
        if(l==-1)return "";
        return string(S.begin()+l,S.begin()+r+1);
    }
};
全部评论

相关推荐

本人一直追求WLB,对大小周深恶痛疾,刷到小红书说取消大小周大喜,看来跳槽的选择又多一个了
一枚大铁锤:至于冲不冲小红书,这是个问题,我先声明我不是这方面的专家,我觉得这件事还是要慎重评论,你问我为什么不给出回答,因为我一开始就说了,我不是这方面的专家
点赞 评论 收藏
分享
FieldMatching:看成了猪头顾问,不好意思
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务