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 =
T =
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 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.
Solution:O(m*n)
public class Solution {
public String minWindow(String S, String T) {
if(S == null || T == null || S.length()==0 || T.length()==0)
return "";
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0;i<T.length();i++){
if(map.containsKey(T.charAt(i)))
map.put(T.charAt(i), map.get(T.charAt(i))+1);
else
map.put(T.charAt(i), 1);
}
int count = 0;
int pre = 0;
String ret = "";
int minLen = S.length()+1;
for(int i=0;i<S.length();i++){
if(map.containsKey(S.charAt(i))){
map.put(S.charAt(i),map.get(S.charAt(i))-1);
if(map.get(S.charAt(i))>=0)
count++;
while(count == T.length()){
if(map.containsKey(S.charAt(pre))){
map.put(S.charAt(pre),map.get(S.charAt(pre))+1);
if(map.get(S.charAt(pre))>0){
if(minLen>i-pre+1) {
ret = S.substring(pre,i+1);
minLen = i-pre+1;
}
count--;
}
}
pre++;
}
}
}
return ret;
}
}
沒有留言:
張貼留言