最小覆盖子串

/*
*   整体思路：将要匹配的模板T的各个字符出现的次数保存到hash中，然后利用双指针，其中左指针从左到右遍历
    遍历过程为左指针固定住，右指针左指针位置开始向右移动，不断将当前字符更新到temphash中，然后不断对比tempHash
    是否已经全部匹配，是则与 目前最短的返回结果对比，判断是否需要更新
*/

//更新hash表，根据flag来递增或递减。
//argc:flag  1-递增     -1-递减
void refreshHash(int *hash, char num, int flag){
    if(num >= 'A' && num <= 'Z'){
        flag == 1 ? (hash[num - 'A' +  0]++) : (hash[num - 'A' +  0]--);
    }else{
        flag == 1 ? (hash[num - 'a' + 26]++) : (hash[num - 'a' + 26]--);
    }
}
void copyHash(int *srcHash, int *detHash){
    for(int i=0; i<=51; i++){       //粗心的bug,之前一直是i<51，匹配字符串出现z无法进行匹配，
        detHash[i] = srcHash[i];
    }
}
//对比hash是否全部都小于0
//如果有大于0的值则表示hash还有数据未匹配，返回-1
//如果均小于0则表示已完全匹配，返回0；
int compareHash(int *hash){
    for(int i=0; i<=51; i++){
        if(hash[i] > 0)
            return -1;
    }
    return 0;
}
void testPrint(char* startChar, int len){
    for(int i=0; i<len; i++){
        printf("%c", startChar[i]);
    }
    printf("\r\n");
}


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param S string字符串 
 * @param T string字符串 
 * @return string字符串
 */
char* minWindow(char* S, char* T ) {
    // write code here
    int hash[52] = {0};
    int tempHash[52] = {0};
    char* retTemp = S; //临时返回结果
    char* retStr;
    int retLen = 10000; //返回长度，初始化为最大
    char* temp;

    temp = T;
    while(*temp != '\0'){           //将T的参数保存到hash中
        refreshHash(hash, *temp, 1);
        temp++;
    }

    while(*S != '\0'){
        copyHash(hash, tempHash);       //每次更新左指针S后，需要将T的hash覆盖tempHash
        temp = S;                       //更新右指针
        while(*temp != '\0'){           //双指针，此时S为左指针，temp为右指针
            refreshHash(tempHash, *temp, -1);   //根据右指针的字符，更新tempHash，此时为没找到一个字符减去1
            if(0 == compareHash(tempHash)){     //判断是否匹配完成，即tempHash全部值小于0
                if(retLen > (temp - S + 1)){    //判断当前匹配的字符串是否最短，是则更新
                    retLen = (temp - S + 1);
                    retTemp = S;
                    // testPrint(retTemp, retLen);  //测试打印
                    break;              //切记需要跳出，让左指针S能够更新
                }
            }
            temp++;                     //更新右指针
        }
        S++;                            //更左指针
    }


    if(retLen == 10000){                //如果返回长度仍为初始值，则表示找到匹配字符串，返回结束符
        retStr = (char*)malloc(sizeof(char));
        retStr[0] = '\0';
        return retStr;
    }else{                              //如果成功匹配字符串
        retStr = (char*)malloc(sizeof(char)*(retLen+1));    //动态申请返回字符串的空间，需要+1用来存储结束符
        for(int i=0; i<retLen; i++){   
            retStr[i] = retTemp[i];
        }
        retStr[retLen] = '\0';
        return retStr;
    }   
}

char* minWindow(char* S, char* T ) {
    // write code here
    int lens = strlen(S);
    int lent = strlen(T);
    if(lent == 0)return "";
    if(lent == 1){
        for(int i=0;i<lens;i++)if(S[i] == T[0]){
            S[i+1] = '\0';
            return (char*)&S[i];
        }
        return "";
    }
    if(lens<lent)return "";
    ///////////////////////////////////////////////////////////
    int book[60] = {0};
    memset(book, 0, 60);

    for(int i=0;i<lent;i++){
        book[T[i]-'A']++;//count required items in T
    }
    
    int left = 0;
    int right = 0;
    int temp_right,temp_left,temp_dis;
    temp_dis = lens;
    char * rrr;
    int unmatch_count = 0;
    
    book[S[right]-'A']--;//initial in
    while(right<lens-1 && left<=right){
        while(right<lens){//move right until match
            unmatch_count = 0;
            //book[S[right]-'A']--;
            for(int i=0;i<lent;i++){
                if (book[T[i]-'A']>0)unmatch_count++;
            }
            if(unmatch_count){
                right++;
                book[S[right]-'A']--;//in
            }
            else break;//matched window
        }
        
        if(unmatch_count && temp_dis == lens)return "";
        else{//move left while keep matched
            while(book[S[left]-'A']<0 && left<right){
                book[S[left]-'A']++;//out
                left++;
            }
        }
        if((right-left)<temp_dis){
            temp_left = left;
            temp_right = right;
            temp_dis = right-left;
        }
        //move left to be unmatched again
        book[S[left]-'A']++;//out
        left++;
    }
    
    rrr = (char*)&S[temp_left];
    S[temp_right+1]='\0';
    return rrr;//
}

//要达到O(n)的优化效果，需要使用滑动窗口
char* minWindow(char* S, char* T ) {
    int left = 0, right = 0;//窗口的左右指针
    int i = 0, j = 0, k = 0;
    //两个字符串长度
    int S_len = strlen(S);
    int T_len = strlen(T);
    int flag = 0;
    //记录能包含子串的窗口个数以及其中最小的左右边界
    int min_l = 0, min_r = S_len, count = 0;    
    int arr[T_len][2];//记录子串中的字符和需要的数量
    int char_need[128];//记录各字符的数量
    int need_count;//子串T中不同字符的个数
    for(i = 0; i < 128; i ++)
    {
        *(char_need + i) = 0;
    }
    //借助char_need数组统计子串中的字符和需要的数量并拷贝到arr数组中
    for(i = 0, j =0; i < T_len; i ++)
    {
        if(*(char_need + (*(T + i))) == 0)
        {
            *(*(arr + (j ++))) = *(T + i);
        }
        *(char_need + (*(T + i))) += 1;
    } 
    for(i = 0; i < j; i ++)
    {
        *(*(arr + i) + 1) = *(char_need + (*(*(arr + i))));
        *(char_need + (*(*(arr + i)))) = 0;

    }
    need_count = j;
    //窗口滑动的过程
    while(left < S_len)
    {
        flag = 0;
        //向右移动right直到窗口中包含了子串中的所有字符，求出right位置
        while(!flag && right < S_len) 
        {
            *(char_need + (*(S + right))) += 1;
            flag = 1;
            for(i = 0; i < need_count; i ++)
            {
                //窗口中的字符与arr数组的比较
                if(*(char_need + (*(*(arr + i)))) <  *(*(arr + i) + 1))
                {
                    flag = 0;
                }
            }
            if(flag) 
            {
                count ++;//窗口数量加一
                break;
            }
            right ++;
        }
        //向右移动left,使得窗口既能满足需求同时又最小
        if(!flag) break;
        flag = 1;
        while(flag && left < right) 
        {
            *(char_need + (*(S + left))) -= 1;
            flag = 1;
            for(i = 0; i < need_count; i ++)
            {
                //窗口中的字符与arr数组的比较
                if(*(char_need + (*(*(arr + i)))) <  *(*(arr + i) + 1))
                {
                    flag = 0;
                }
            }
            if(!flag) 
            {
                break;
            }
            left ++;
        }
        //判断此时窗口是否最小
        if(right - left < min_r - min_l)
        {
            min_l = left ;
            min_r = right ;
        } 
        窗口整体向右移动一格
        left ++;
        right ++;
    }
    if(count)//如果有过匹配的窗口
    {
        char *ans = (char *)malloc(sizeof(char)*(min_r - min_l + 2));
        for(i = min_l, j = 0; i <= min_r; i ++, j ++)
        {
            *(ans + j) = *(S + i);
        }
         *(ans + j) = '\0';
        return ans;
    }
    else
    {
        return "";
    }
}