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.
思路:涉及到2点: 1. Hash, 保证查找为 O(1). 2. S 中设置两指针,根据长度确定右边指针位置;根据若去掉该字符,则该字符在 window 中出现次数将小于在 T 中出现的次数确定左边指针位置。
class Solution { public: string minWindow(string S, string T) { if(T == "" || S == "") return ""; string s; int ch[2][‘z‘+1] = {0}; for(int i = 0; i < T.size(); ++i) ++ch[0][T[i]]; int first = 0, cnt = 0; for(int second = 0; second < S.size(); ++second) { if(ch[0][S[second]]) { if(ch[0][S[second]] > ch[1][S[second]]) ++cnt; ++ch[1][S[second]]; } if(cnt == T.size()) { while(ch[0][S[first]] == 0 || ch[1][S[first]] > ch[0][S[first]]) { if(ch[1][S[first]] > ch[0][S[first]]) ch[1][S[first]]--; ++first; } string tem = S.substr(first, second-first+1); if(s == "" || s.size() > tem.size()) s = tem; --ch[1][S[first++]]; --cnt; } } return s; } };