首页 > 代码库 > 【LeetCode】Minimum Window Substring
【LeetCode】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.
由于大小写字母的ASCII码不大于128，因此开辟两个数组存储信息。
needCount数组存储T字符串每个字符出现次数。例如：needCount[‘A‘]=5意为T中A出现5次。
findCount数组存储S字符串在[begin,end]窗口内每个字符出现次数。
算法核心思想如下：
在保证[begin,end]窗口包含T中所有字符的条件下，延伸end，收缩begin。
进行一次扫描后，记录符合条件的最小窗口(end-begin+1)表示的字符串。
有个问题：怎样才知道[begin,end]窗口包含了T中所有字符？
我使用count记录“有效”字符数，当count达到T.size()时，即可说明[begin,end]包含了T。
“有效”的意思是指，当前延伸得到的S[end]字符，使得[begin,end]更进一步包含T，而不是重复劳动。
比如说，T="a", [begin,end]已经包含"a",再延伸得到"aa"，只是无效操作，并没有使得[begin,end]更接近T,有效字符数仍为1.
代码如下：部分思想借鉴jellyyin的博客。
class Solution {public: string minWindow(string S, string T) { int size1 = S.size(); int size2 = T.size(); vector<int> needCount(128, 0); //A~Z,a~z ascii code is less than 128 vector<int> findCount(128, 0); //construct needCount, which represents chars in T for(int i = 0; i < size2; i ++) needCount[T[i]] ++; int minBegin = 0; //min window begin position int minEnd = size1 - 1; //min window end position int minWidth = INT_MAX; //INT_MAX means not exist int begin = 0; //cur window begin position int end = 0; //cur window end position int width = end-begin+1; //number of chars in T that included in S(begin, width) int curCount = 0; for(; end < size1; end ++) { //skip chars not in T while(end < size1 && needCount[S[end]] == 0) end ++; //to here, S[end] in T findCount[S[end]] ++; //only needCount[S[end]] chars are needed to find if(findCount[S[end]] <= needCount[S[end]]) curCount ++; if(curCount == size2) {//find all, and shrink the window //check shrink1 and shrink2 alternately while(begin < end) { if(needCount[S[begin]] == 0) {//shrink 1: skip needless chars in cur window begin ++; continue; } //to here, needCount[S[begin]] != 0 else if(findCount[S[begin]] > needCount[S[begin]]) {//shrink 2: skip redundant chars in cur window findCount[S[begin]] --; begin ++; continue; } else break; } //shrink finish width = end-begin+1; if(width < minWidth) { minBegin = begin; minEnd = end; minWidth = width; } } } if(minWidth == INT_MAX) return ""; else return S.substr(minBegin, minWidth); }};
【LeetCode】Minimum Window Substring