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.
题意:找到S串中包含T的最短的子串,可以不按顺序思路:还是双指针发处理,尾指针先找到已经包含了T串的位置,然后头指针再不停的收缩,标记的方式就是记录字符出现的次数
class Solution { public: int count1[256]; int count2[256]; string minWindow(string S, string T) { if (T.size() == 0 || S.size() == 0) return ""; memset(count1, 0, sizeof(count1)); memset(count2, 0, sizeof(count2)); for(int i = 0; i < T.size(); i++) { count1[T[i]]++; count2[T[i]] = 1; } int count = T.size(); int start = 0; int minSize = INT_MAX; int minStart; for(int end = 0; end < S.size(); end++) { if (count2[S[end]] > 0) { count1[S[end]]--; if (count1[S[end]] >= 0) count--; } if (count == 0) { while(1) { if (count2[S[start]] > 0) { if (count1[S[start]] < 0) count1[S[start]]++; else break; } start++; } if (minSize > end - start + 1) { minSize = end - start + 1; minStart = start; } } } if (minSize == INT_MAX) return ""; return S.substr(minStart, minSize); } };