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

题目：

 

 

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).

 

For example,

S = "ADOBECODEBANC"

T = "ABC"

 

Minimum window is "BANC".

 

Note:

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

 

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

 

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

 

 

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

 

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

 

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

 

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 "";  
    }  
};  

 

补充：移动开发 , 其他 ,