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.
题解:参考leetcode给出的解答,实现了O(n)的算法。
用到的主要变量如下:
设置一个Map:ToFind记录T中出现的字符的种类和个数,我们需要在S中找到这些字符。
设置另一个Map:hasFound记录当前窗口中包含的字符的种类和个数。
这两个Map,结合一个变量count——在当前窗口中找到的T中的字符个数,我们就可以判断当前窗口是否包含T中所有的字符了。
算法的主要过程如下:
当前窗口的起始和结束位置都在S(0)处;
当窗口中没有包含T中所有的字符时(count<T.length),扩展窗口的右端end,直到窗口中包含了T中所有的变量。
此时窗口不一定是最小的,因为左端还有可能缩进,根据窗口的左端变量begin所指的元素,把窗口的左端尽可能右移。
得到一个包含T的窗口,跟最小的窗口比较,如果比最小的窗口小,就更新最小的窗口。
举个例子:S = "acbbaca" , T = "aba"。
如上图所示,end从初始的位置扩展到下面的图中的位置时候,窗口包含了T中所有的字符,而且begin也无法挪动了,此时得到一个最小窗口长度为5;
接下来继续移动end直到下一个包含在T里面的元素处(见第二幅图),然后把begin尽可能往右移动(见第三幅图),得到一个新的当前最小窗口baca,由于它比最小窗口acbba短,所以更新最小窗口为baca。算法结束。
所以我们可以看出begin只有在找到T的时候才右移收缩窗口,而end一直后移。在找到第一个窗口后,end每移动到一个T里面包含的元素处,就会有一个新的窗口(比如上述end从索引为4的地方挪动到索引为6的地方)。
代码如下:
public class Solution {
public String minWindow(String S, String T) {
HashMap<Character, Integer> needToFind = new HashMap<Character, Integer>();
HashMap<Character, Integer> hasFound = new HashMap<Character, Integer>();
int count = 0; for(int i = 0;i < T.length();i++){
char ch_t = T.charAt(i);
if(!needToFind.containsKey(ch_t)){
needToFind.put(ch_t, 1);
hasFound.put(ch_t, 0);
}
else {
needToFind.put(ch_t, needToFind.get(ch_t)+1);
}
} int minWindowBegin = -1;
int minWindowEnd = S.length();
int minWindowLen = S.length();
for(int begin = 0,end = 0; end < S.length();end++){
char char_end = S.charAt(end);
//skip character not in T
if(!needToFind.containsKey(char_end))
continue;
hasFound.put(char_end, hasFound.get(char_end)+1);
if(hasFound.get(char_end) <= needToFind.get(char_end))
count++; if(count == T.length()){
//narrow down the window as much as possible
char char_begin = S.charAt(begin);
while(!needToFind.containsKey(char_begin) || hasFound.get(char_begin) > needToFind.get(char_begin)){
if(needToFind.containsKey(char_begin) && hasFound.get(char_begin) > needToFind.get(char_begin)){
hasFound.put(char_begin, hasFound.get(char_begin)-1);
}
begin++;
char_begin = S.charAt(begin);
} int windowLen = end - begin + 1;
if(windowLen <= minWindowLen){
minWindowBegin = begin;
minWindowEnd = end;
minWindowLen = windowLen;
} }
} if(count == T.length()){
StringBuffer sbBuffer = new StringBuffer();
for(int i = minWindowBegin;i<=minWindowEnd;i++)
sbBuffer.append(S.charAt(i));
return sbBuffer.toString();
}
else
return "";
}
}