题解 | #最小覆盖子串#
最小覆盖子串
https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac
import java.util.*;
public class Solution {
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
public String minWindow (String S, String T) {
// write code here
Map<Character,Integer> s_map = new HashMap<>();
Map<Character,Integer> t_map = new HashMap<>();
//T中的数据存入t_map
for(int i = 0;i<T.length();i++){
t_map.put(T.charAt(i), t_map.containsKey(T.charAt(i)) ? t_map.get(T.charAt(i))+1 : 1 );
}
int left = 0;
int right = 0;
int result_length = Integer.MAX_VALUE;
String ans = "";
while(right < S.length()){
s_map.put(S.charAt(right), s_map.containsKey(S.charAt(right)) ? s_map.get(S.charAt(right)) +1 : 1 );
while(isCover(s_map,t_map)){
if(result_length > right - left +1){
result_length = right - left +1;
ans = S.substring(left,right+1);
}
s_map.put(S.charAt(left), s_map.get(S.charAt(left)) - 1 );
if(s_map.get(S.charAt(left)) == 0){
s_map.remove(S.charAt(left));
}
left++;
}
right++;
}
return ans;
}
public boolean isCover(Map<Character,Integer> s_map,Map<Character,Integer> t_map){
for(Character key : t_map.keySet()){
if(!s_map.containsKey(key)){
return false;
}else if(s_map.get(key) < t_map.get(key)){
return false;
}
}
return true;
}
}
”