题解 | #最小覆盖子串#
最小覆盖子串
https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac
评论区巴拉出来的 ，还是想了很久
char* minWindow(char* S, char* T ) {
/*hash T字符串*/
char T_hash[256] = {0};
int i=0,j=0;
while(T[i] != '\0'){
T_hash[T[i++]]++;
}
/*把T字符串中出现过的单词按顺序排列*/
char T_word[100] = {0};
for(i=0;i<256;i++){
if(T_hash[i] != 0)
T_word[j++] = i;
}
/*
滑动窗口比较，双指针
XDOYE，左指针不动，右指针后移；当XDOYEZ时，右指针不动，左指针后移；
左指针后移一位变成DOYEZ，此时match != 3，右指针后移
*/
int T_Long = j,left = 0,right = 0,match = 0;
char window[256] = {0};
int width=0,minwidth = strlen(S)+1;
static char res[2000]={0};//一定要用static，2000太大
while(S[right] != '\0'){
window[S[right++]]++;
match = 0;
for(i=0;i<T_Long;i++){
if(window[T_word[i]]-T_hash[T_word[i]]>=0)
match++;
else match--;
}
while(match == T_Long){
width = right-left;
if(minwidth > width){
minwidth = width;
memset(res,'\0',sizeof(res));
for(i=0,j=left;j<right;i++,j++){
res[i] = S[j];
}
res[i]='\0';
}
window[S[left++]]--;
match = 0;
for(i=0;i<T_Long;i++){
if(window[T_word[i]]-T_hash[T_word[i]]>=0)
match++;
else match--;
}
}
}
return res;
}
