题解 | #最小覆盖子串#

/**
思路：
	移动窗口，判断T是否在窗口S子串内；窗口最小为strlen(T)，最大为strlen(S)。
	判断方法：将字符串转换成52位的数组(字符串只含a-zA-Z)TArr和SArr,比较TArr和SArr。
**/
#include <string.h>
#define ARR_SIZE 52

void str2ints(char* str, int len, int *arr) {
    for (int i = 0; i<len;i++) {
        char c = str[i];
        if (c >= 'a' && c <= 'z') {
            arr[c-71]++;
        } else if (c >= 'A' && c <= 'Z') {
            arr[c-65]++;
        }
    }
}
bool compareArr(int *n,int *ws)
{
    for(int i=0;i<ARR_SIZE;i++)
    {
        if(n[i]>ws[i])
        {
            return false;
        }
    }
    return true;
}
char* minWindow(char* S, char* T ) {
    // write code here
    if(!S || !T || strlen(S)<strlen(T))
    {
        return "";
    }
    int slen = strlen(S);
    int tlen = strlen(T);

    int i,j;
    int TArr[52] = {0};
    str2ints(T,tlen,TArr);
    for(i=tlen;i<=slen;i++)
    {
        for(j=0;j<=slen-i;j++)
        {
            int SArr[52] = {0};
            str2ints(S+j, i,SArr);
            if(compareArr(TArr, SArr))
            {
                char *res = (char *)malloc(sizeof(char)*slen);
                memset(res, 0x0, sizeof(char)*slen);
                memcpy(res, S+j, sizeof(char)*i);
                return res;
            }
        }
    }
    return "";
}