首页 > 代码库 > Minimum Window Substring
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.
我们下面使用 S = "acbbaca" and T = "aba" 来演示这个算法。基本思路是在遍历S的过程中,使用两个指针(合法window的begin和end索引)和两个table(needToFind和hasFound),needToFind保存T中每个字母的个数(二娃:相当于我们的needToFill),hasFound保存当前收集到的每个字母的个数。我们也同时使用一个count变量,用来保存当前收集到的字母总数,但是那些收集过了的字母数并不算在count里面。这样的话,当count等于T.length,那我们就知道遇到一个合法的window了。
我们利用end指针来遍历S,假设当前end指向S中的字母x,如果x是T中的字母,hasFound[x]加一。如果hasFound[x]目前还小于等于needToFind[x](二娃:说明字母x还没有收集全或者刚刚收集全哦),那么我们同时也增加count。当合法window的条件满足,也就是count等于T.length,我们立即递增begin指针,并且保证在递增的过程中始终有count等于T.length。
在递增begin指针的过程中,我们怎么样才能保证“始终有count等于T.length”呢?
假设begin指向字母x,如果hasFound[x]大于了needToFind[x],hasFound[x]减去一,同时递增begin。(二娃:这里很有画面感哦。因为当前遇到的x是冗余的靠左的字母,这里的操作其实等价于前面两个算法中的“删除charAppearanceRecorder中相应的字母的链表头节点”,有点儿像一个是lazy去重,一个是eager去重)否则的话,当前的begin就是window的起始索引了。
接下来我们就可以通过end - begin + 1得到当前window的长度了。这里便可以更新最小window长度。
算法实际上首先找到第一个合法的window,然后在接下来的扫描过程中保持window的合法性(二娃:其实就是count 始终小于等于(当遇到新window)T.length)。
看下面的图图。
i)S = "acbbaca" and T = "aba".
ii)找到第一个合法的window。这里注意我们不能递增begin指针因为hasFound[‘a‘] 等于 needToFind[‘a‘],即2. 如果我们此时递增begin,那就不是合法window了。
iii)找到第二个合法的window。begin指针指向第一个a,hasFound[‘a‘]等于3,而needToFind[‘a‘]等于2,说明这个a是一个冗余的a,我们递减hasFound[‘a‘]同时递增begin。
iv)我们也需要跳过那些不在T中的字母,例如上面的c。现在beging指向了b,hasFound[‘b‘]等于2,大于了needToFind[‘b‘],说明这也是一个冗余的b,我们递减hasFound[‘a‘]同时递增begin。
v)begin指向b,这时候hasFound[‘b‘]等于needToFind[‘b‘]。不能再减了,同时begin也不能再次移动了,这里就是一个短window的起点位置。
begin和end都最多前进N次,从而整个算法执行小于2N. 复杂度是O(N)。
class Solution {private: int count1[256]; int count2[256];public: string minWindow(string S, string T) { // Start typing your C/C++ solution below // DO NOT write int main() function 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]]++; } 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(true) { 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 ""; string ret(S, minStart, minSize); return ret; }};
Minimum Window Substring