[LeetCode] find the Minimum window in s which contains all elements from T

Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n).

eg,

S = “ADOBECODEBANC”

T = “ABC”

Minimum window is “BANC”.

其实上，这个就相当于编程之美上的最短摘要的生成问题，这里其实是简化了的版本。因为对字符进行hash映射其实比对单词映射要简单得多。当然如果换成了单词的话，可以用map容器，一样的操作思路。

OK，下面说一下思路，用p1,p2两个一前一后的指针，p1,p2中间的字符形成了一个滑动窗口。

1、当T中的字符未被完全包含时，计入p2字符。

2、当T中的字符被全部包含时，逐个去除p1字符，直到某个T中的字符不在包含于p1,p2所涵盖的窗口。

3、边界处理。如果T不包含任何字符，则Ans为0。如果Src不包含任何字符，则Ans为INT_MAX。不管哪种情况Begin指针都初始化为Src

核心参考代码如下，引用请注明出处：

 

int FindShortestTemp(char *Src, char *T, char *&Begin)  
{  
    assert(Src && T);  
    int Num = strlen(T);  
    Begin = Src;  
    if(Num <= 0)  
    {  
        return 0;//T不包含任何字符，返回0  
    }  
    int Count = 0;  
    int Ans = strlen(Src);  
    if(Ans <= 0)  
    {  
        return INT_MAX;//Src不包含任何字符，返回INT_MAX  
    }  
  
    char *p1, *p2;  
    p1 = p2 = Src;  
    InitFlag(T);  
    while(*p2 != '\0')  
    {  
        while(*p2 != '\0' && Count < Num)  
        {  
            if(Flag[*p2 - 'A'] > -1)  
            {  
                ++Flag[*p2 - 'A'];  
                if(Flag[*p2 - 'A'] == 1)  
                {  
                    ++Count;  
                }  
            }  
            ++p2;  
        }  
        if(Count < Num)//p2到达最后了，但没有找到全部字符  
        {  
            return Ans;  
        }  
        while(p1 < p2 && Count >= Num)  
        {  
            if(Flag[*p1 - 'A'] > -1)  
            {  
                --Flag[*p1 - 'A'];  
                if(Flag[*p1 - 'A'] == 0)  
                {  
                    --Count;  
                }  
            }  
            ++p1;  
        }  
        //更新Ans  
        if((p2 - p1 + 1) / sizeof(char) < Ans)  
        {  
            Begin = p1 - 1;  
            Ans = p2 - Begin;  
        }  
        if(*p2 == '\0')//p2正好是最后一个应该包含的元素  
        {  
            return Ans;  
        }  
    }  
    return Ans;  
}  

 

 

照旧，最后给出一些辅助函数以及main函数的调用：

#include<stdio.h>  
#include<assert.h>  
#include<string.h>  
#include<limits.h>  
  
const int MAX_N = 30;  
int Flag[MAX_N];//T里面的标记为0，其余标记为-1  
  
void InitFlag(char *T)  
{  
    int i;  
    for(i = 0; i < MAX_N; ++i)  
    {  
        Flag[i] = -1;  
    }  
    while(*T != '\0')  
    {  
        Flag[*T - 'A'] = 0;  
        ++T;  
    }  
}  
  
void Print(char *Src, int nLen)  
{  
    assert(Src && nLen >= 0);  
    for(int i = 0; i < nLen; ++i)  
    {  
        putchar(Src[i]);  
    }  
    printf("\n");  
}  
  
int main()  
{  
    char Src[MAX_N];  
    char T[MAX_N];  
    char *Begin = NULL;  
    int Ans = 0;  
    while(scanf("%s %s", Src, T) != EOF)  
    {  
        Ans = FindShortestTemp(Src, T, Begin);  
        if(Ans < INT_MAX)  
        {  
            printf("%d\n", Ans);  
            Print(Begin, Ans);  
        }  
    }  
    return 1;  
}  

 

 

补充：综合编程 , 其他综合 ,