2014年5月13日星期二

Loop Solution - Minimum Window Substring ***??

class Solution {
public:
    string minWindow(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (S.size()<T.size()){return "";}
           
        map<char,int>mp; // store chars occurrence of T
        for(int i=0;i<T.size();i++){mp[T[i]]++;}
       
        int res_len=INT_MAX; // result length
        int res_p=0;//result start posiion
       
        int p=0; //pointer start
        int q=S.size()-1; //pointer end
       
        while (mp[S[p]]==0){if(p>=S.size()){return "";} p++;} //remove irralevent starting chars
        while (mp[S[p]]==0){q--;if(q<0){return "";}} // remove irralevent ending chars
       
        map<char,int> tab; //store chars occurrence of S[p:q]
        for (int i=p;i<=q;i++){tab[S[i]]++;}
                   
        while (tab[S[q]]>mp[S[q]] || mp[S[q]]==0){ // move q to left find the 1st covered substring
           tab[S[q]]--;
           q--;
        }
           
        for (int i=0;i<T.size();i++){  // if no covered substring found, return ""
            if (tab[T[i]]<mp[T[i]]){return "";}
        }
   
        if (q-p+1<res_len){res_len=q-p+1; res_p=p;} //store the result
       
       
        while (p<q){
            if (q-p+1<res_len){res_len=q-p+1; res_p=p;} //store the result
            if (mp[S[p]]==0){p++;continue;} // if current char is not in T, go next
            if (tab[S[p]]>mp[S[p]]){tab[S[p]]--;p++;continue;} // if more chars in this substring, go next
           
            q++;
            while (q<S.size() && S[q]!=S[p]){ if (mp[S[q]]>0){tab[S[q]]++;} q++;} //move q to find a substring covers T
            if (q>=S.size()){q=S.size()-1;}else{tab[S[q]]++;}
           
            if (S[q]==S[p]){ tab[S[p]]--; if (tab[S[p]]<mp[S[p]]){break;} p++;continue;}      
            break;
        }
       
        return S.substr(res_p,res_len);
    }
};

没有评论: