Given a string S and a string T.
Find the minimum window in S which contains all the characters in T
with complexity O(n).
Example, S = "ADOBECODEBANC", T = "ABC", Minimum window is "BANC".
public String minWindow(String s, String t) {
HashMap goal = new HashMap<>();
int goalSize = t.length();
int minLen = Integer.MAX_VALUE;
String result = "";
//target dictionary
for(int k=0; k map = new HashMap<>();
for(int j=0; jgoal.get(s.charAt(i))){
char pc = s.charAt(i);
if(goal.containsKey(pc) && map.get(pc)>goal.get(pc)){
map.put(pc, map.get(pc)-1);
}
i++;
}
if(minLen>j-i+1){
minLen = j-i+1;
result = s.substring(i, j+1);
}
}
}
return result;
}
No comments:
Post a Comment