题目:
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.
解题:
string minWindow(string S, string T) { if(S.size() == 0)return ""; if(S.size() < T.size())return ""; int expect[128] = {0}; int appear[128] = {0}; int i; int cnt = 0; int start = 0; int min_start = 0; int min_length = INT_MAX; for(i = 0; i < T.size(); i++){ expect[T[i]]++; } for(i = 0; i < S.size(); i++){ if(expect[S[i]] > 0){ appear[S[i]] ++; if(appear[S[i]] <= expect[S[i]]) cnt++; } if(cnt == T.size()){ while(appear[S[start]] > expect[S[start]] || expect[S[start]] == 0){ appear[S[start]]--; start++; } if(min_length > (i - start + 1)){ min_length = i - start + 1; min_start = start; } } } if(min_length == INT_MAX)return ""; return S.substr(min_start,min_length); }
30ms,还有优化的空间。