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.
class Solution {
private:
int hashs[
256];
int hasht[
256];
inline
bool check()
{
for(
int i=
0;i<
256;i++)
if(hashs[i]<hasht[i])
return false;
return true;
}
public:
string minWindow(
string S,
string T)
{
for(
int i=
0;i<
256;i++)
{
hashs[i]=
0;
hasht[i]=
0;
}
for(
int i=
0;i<T.size();i++)
hasht[T[i]]++;
int minl=-
1;
int minr=S.length();
for(
int i=
0;i<S.size();i++)
hashs[S[i]]++;
if(!check())
return "";
int l=
0;
int r=
0;
for(
int i=
0;i<
256;i++) hashs[i]=
0;
hashs[S[
0]]=
1;
while(
true)
{
if(check())
{
if(r-l<minr-minl)
{
minl=l;
minr=r;
if(minr-minl+
1==T.length())
break;
}
hashs[S[l]]--;
l++;
}
else {
r++;
if(r==S.length())
break;
hashs[S[r]]++;
}
}
if(minl==-
1)
return "";
else return S.substr(minl,minr-minl+
1);
}
};
Minimum Window Substring,布布扣,bubuko.com
Minimum Window Substring
原文：http://www.cnblogs.com/erictanghu/p/3759497.html
