leetcode：Minimum Window Substring（最小覆盖子串）【面试算

来源：未知责任编辑：责任编辑发表时间:2013-11-26 22:13　点击:次

p>题目：

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

p>For example,

p>S = "ADOBECODEBANC"

p>T = "ABC"

p>Minimum window is "BANC".

p>Note:

p>If there is no such window in S that covers all characters in T, return the emtpy string "".

p>If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

p>题意就是在S中选一个最小的子串，使得包含T中所有的字母。

p>做法就是双指针的贪心做法，找到以i结尾的最小子串满足条件。

p>minn和left，right分别记录最小子串的最小值和左右位置。

p>data存T串的信息，now存当前i到j的信息，保存的是元素的个数。

p>num记录增加的元素个数是否达到条件。

class Solution {  
public:  
    string minWindow(string S, string T) {  
        int data[260],i,j;  
        memset(data,0,sizeof(data));  
        for(i=0;i<T.length();++i)  
            data[T[i]]++;  
        int now[260],left,right,minn=1<<29,num=0;  
        memset(now,0,sizeof(now));  
        for(i=0,j=0;i<S.length();++i)   
        {  
            if(num<T.length())  
            {  
                if(now[S[i]]<data[S[i]])num++;  
                now[S[i]]++;  
            }  
            if(num==T.length())  
            {  
                while(j<=i&&now[S[j]]-1>=data[S[j]])  
                {  
                    --now[S[j]];  
                    ++j;                      
                }  
                if(minn>i-j+1)left=j,right=i,minn=i-j+1;  
            
                while(j<=i&&num==T.length())  
                {  
                    now[S[j]]--;  
                    if(now[S[j]]<data[S[j]])num--;  
                    ++j;  
                }    
            }  
        }  
        string temp;  
        if(minn<1<<29)return temp.assign(S,left,right-left+1);  
        else return "";  
    }  
};