题解 | #最小覆盖子串#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param S string字符串 
 * @param T string字符串 
 * @return string字符串
 */

//哈希表：判断要找的关键字符的出现与否,
// 
//falg:表示T中的字符种数
//flag1:表示滑动窗口目前已经满足T串中要求字符数目的字符种数，当flag1==flag，此时滑动窗口中字符串即是覆盖子串
//整个过程：1.右指针右移找到覆盖子串，2.左指针右移漏掉一些字符(可能包括关键字符)至最小覆盖子串并记录，左指针右移漏掉一位关键字符，右指针再右移找到覆盖子串......
//注：上述过程必能遍历任何最小覆盖子串

char* minWindow(char* S, char* T ) {
    int left=0,right=0,flag=0,flag1=0;  
    int fun[123],i;  
    int smallstr[3]={0};  //记录最小覆盖子串

    for(i=0;i<123;i++) fun[i]=-10001;
    for(i=0;i<strlen(T);i++){    //遍历T字符串，将关键字符的信息存储在哈希表中
        if(fun[T[i]-'0']==-10001) fun[T[i]-'0']=0,flag++; //flag值意为：T中字符的种数  
        fun[T[i]-'0']--;
    }

    for(;;){    //整个过程
    for(;right<strlen(S);right++){ //右指针右移找到覆盖子串
        if(fun[S[right]-'0']!=-10001){
            fun[S[right]-'0']++;
            if(fun[S[right]-'0']==0){
                flag1++;
                if(flag1==flag) break;//当右指针遍历过的字符中，关键字符的种类等于需要的种类，且每种数量都相等，说明已找到覆盖子串
            } 
        } 
    }
    if(right>=strlen(S)) break; //若右指针超出S字符串边界，退出大循环

    for(;;left++){   //左指针右移漏掉一些字符(可能包括关键字符)至最小覆盖子串
        if(fun[S[left]-'0']!=-10001){
            if(fun[S[left]-'0']==0) break;
            else fun[S[left]-'0']--;
        }
    }
    if(smallstr[2]==0) smallstr[2]=right-left+1; //记录下此时的最小覆盖子串
    if(smallstr[2]>=right-left+1){
        smallstr[2]=right-left+1;
        smallstr[0]=left;
        smallstr[1]=right;
    } 
    fun[S[left]-'0']--,flag1--,left++,right++;  //左指针右移漏掉一位关键字符,此时滑动窗口中字符种数减一,右指针右移一位
    if(right>=strlen(S)||left>=strlen(S)) break;
    }
    
    char *p;                            //此时将最小覆盖串复制到p串中，返回p指针
    p=(char*)malloc(strlen(S)*sizeof(char));
    memset(p,'\0',strlen(S)*sizeof(char));

    if(smallstr[2]==0) return p;
    else {
        for(i=0;i<smallstr[2];i++){
            p[i]=S[smallstr[0]+i];
        }
        return p;
    } 
}