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.
Naive Way: In order to find a minimum window, there must be a way to represent the pattern (which is T) here and current accumulate characters set. A map is suitable to deal with that. Map each character to # of its appearance. And then, need to find a way to keep track of every possible position when a match was found and you need to delete the first character from current accumulate char set. A queue is suitable to do that.
A case when S = "bba" and T="ab" leads to this line.
while(isMatch(pattern, cur)){ /* Important Code! */
One shortcoming is isMatch() funciton takes O(T) time.
public class Solution {
public String minWindow(String S, String T) {
Map<Character, Integer> pattern = new HashMap<Character, Integer>();
Map<Character, Integer> cur = new HashMap<Character, Integer>();
Queue<Integer> queue = new LinkedList<Integer>();
int min = Integer.MAX_VALUE;
int begin = 0, end = 0;
// fill in pattern by T
for(int i = 0;i < T.length();i++) addToMap(pattern, T.charAt(i));
// initialize current set
for(int i = 0;i < T.length();i++) cur.put(T.charAt(i), 0);
// go through S to match the pattern by minimum length
for(int i = 0;i < S.length();i++){
if(pattern.containsKey(S.charAt(i))){
queue.add(i);
addToMap(cur, S.charAt(i));
// check if pattern is matched
while(isMatch(pattern, cur)){ /* Important Code! */
if(i - queue.peek() < min){
min = i - queue.peek();
begin = queue.peek();
end = i+1;
}
cur.put(S.charAt(queue.peek()), cur.get(S.charAt(queue.peek()))-1);
queue.poll();
}
}
}
return end > begin?S.substring(begin, end):"";
}
private void addToMap(Map<Character, Integer> map, Character c){
if(map.containsKey(c))
map.put(c, map.get(c)+1);
else
map.put(c,1);
}
private boolean isMatch(Map<Character, Integer> p, Map<Character, Integer> cur){
for(Map.Entry<Character, Integer> entry: p.entrySet())
if(cur.get((char)entry.getKey()) < (int)entry.getValue()) return false;
return true;
}
}
No comments:
Post a Comment