题解 | #最小覆盖子串#

C语言

/*
*   整体思路：将要匹配的模板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;
    }   
}