题解 | #最小覆盖子串#

#include <cstddef>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */

    bool valid(map<char,int>& m,map<char,int>& condition){
	  //检查m字典是否拥有condition里所有的key,且m[key]>=condition[key]
        auto p = condition.begin();
        while(p!=condition.end()){
            const char& key = p->first;
            if(m.find(key)==m.end()){//若m不存在该key
                return false;
            }else if(m[key]<condition[key]){//若m存在该key但value小于要求值
                return false;
            }
            p++;
        }
        return true;
    }

    string minWindow(const string& S, const string& T) {
        // write code here
        map<char,int> needfind,found;
        for(const char& c : T){
            needfind[c]++;
        }
        

        vector<pair<int,int>> targets;//保存所有找到的覆盖子串
        queue<int> foundIndex;

        for(int i=0;i<S.size();i++){

            const char& c = S[i];
            auto p = needfind.find(c);

            if(p!=needfind.end()){//若当前字符在needfind中

                foundIndex.push(i);

                found[c]++;

                while(valid(found, needfind)){

                    int j = foundIndex.front();
                    foundIndex.pop();

                    targets.push_back(make_pair(j,i));

                    found[S[j]]--;

                }
			  
            }
        }

        if(targets.empty()){
            return "";
        }
		
	  	//按照覆盖子串的长度升序排序
        sort(targets.begin(),targets.end(),
        [](const pair<int,int>& a,const pair<int,int>& b)->bool{
            return (a.second-a.first) < (b.second-b.first);
        });

        const int& a = targets[0].first;
        const int& b = targets[0].second;
        return S.substr(a,b-a+1);

    }
};