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.
要求复杂度为O(n),只要扫描一遍数组即可,大致做法是设一个start和一个end表示窗口的起始与结束位置,先从先向后匹配end,当找到可容纳T的窗口后再从前而匹配start,去掉无用的元素。具体做法为使用两个哈希表hasCvd与need2Cv,分别表示已经找到的某个字母的匹配与需要找到的匹配。
1 class Solution { 2 public: 3 string minWindow(string S, string T) { 4 int start = 0, end = 0; 5 int min_start = 0, min_end = 0; 6 int min_len = INT_MAX; 7 vector<int> hasCvd(256 ,0); 8 vector<int> need2Cv(256, 0); 9 for (int i = 0; i < T.length(); ++i) { 10 ++need2Cv[T[i]]; 11 } 12 int validCnt = 0; 13 for (end = 0; end < S.length(); ++end) { 14 ++hasCvd[S[end]]; 15 if (need2Cv[S[end]] == 0) continue; 16 if (hasCvd[S[end]] <= need2Cv[S[end]]) ++validCnt; 17 if (validCnt == T.length()) { 18 while(hasCvd[S[start]] > need2Cv[S[start]]) { 19 --hasCvd[S[start]]; 20 ++start; 21 } 22 if(min_len > (end - start)) { 23 min_len = end - start + 1; 24 min_start = start; 25 min_end = end; 26 } 27 } 28 } 29 return (min_len == INT_MAX) ? "" : S.substr(min_start, min_len); 30 } 31 };