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.
这题需要设置双指针,一个作为所求window substring的开始处下标start,一个作为所求window substring的结束处下标end。两个下标最开始都指向S[0]。移动过程如下:
1)向前移动end,伸展window substring,直到该子字符串完全覆盖T;
2)向前移动start,收缩window substring,直到该子字符串刚好完全覆盖T。
这样得到的一个window substring的长度具有极小值,是所求全局最短子字符串的一个candidate。
重复以上两步,获得更多的candidate,不断更新全局最短子字符串,直到end越出S的右边界。
注意题目这里有点没说明确,如果一个字符在T中重复了N次,那么所求的子字符串内也必须让该字符重复出现N次。本来一开始用了HashSet,后来发现不光要记录一个字符是否在T中出现,并且还得记录出现的次数,所以后来换成了HashMap,key和value是T里出现的字符和次数。一开始做了个word count。(让人不禁联想到了MapReduce,汗~)
为了判断子字符串是否覆盖T,维护了一个计数器,每找到一次字符匹配,就加1,直到等于T的字符串长度,但是匹配一旦超过了T本身含有的该字符,就不再追加。
public String minWindow(String S, String T) { boolean found = false; String ret = S; String curStr; // record the character frequencies for T HashMap<Character, Integer> map = new HashMap<Character, Integer>(); for (int i = 0; i < T.length(); i++) { char c = T.charAt(i); if (map.containsKey(c)) { map.put(c, map.get(c) + 1); } else { map.put(c, 1); } } int start = 0, end = 0, count = 0; // in order to cover T, extend the current string by moving the end forward while (end < S.length()) { char cEnd = S.charAt(end); if (map.containsKey(cEnd)) { // the # of this character unmatched in T int num1 = map.get(cEnd); num1--; map.put(cEnd, num1); if (num1 >= 0) { count++; // if T can be covered by the current substring while (count == T.length()) { found = true; // shrink the current substring by moving the start forward char cStart = S.charAt(start); if (map.containsKey(cStart)) { // the # of this character unmatched again in T int num2 = map.get(cStart); num2++; map.put(cStart, num2); // not covered again if (num2 > 0) { count--; curStr = S.substring(start, end + 1); if (curStr.length() < ret.length()) { ret = curStr; } } } start++; } } } end++; } if (found) return ret; else return ""; }