Leetcode76最小覆盖子串

最小覆盖子串"/>

Leetcode76最小覆盖子串

思路：滑动窗口思想

1. 滑动窗口是什么：用一个滑动窗口为覆盖目标子串的字符串

2.怎么移动窗口：当不满足覆盖时右指针移动扩大范围，当覆盖了就移动左指针缩减范围直到再次不覆盖

3. 怎么判断是否覆盖：这里使用两个哈希表，一个保存目标子串字符数，一个保存窗口内的字符数，注意是窗口内的，因为需要用窗口的和目标子串进行比较来控制移动

4. 怎么控制循环：外层循环while(right<len) right++，内层循环符合覆盖且left<right

class Solution {Map<Character,Integer> map = new HashMap<Character,Integer>();Map<Character,Integer> target = new HashMap<Character,Integer>();public String minWindow(String s, String t) {if(s.length() == 1 && s.equals(t)){return s;}int left = 0;//初始化为-1int right = -1;char[] str = s.toCharArray();char[] tc = t.toCharArray();//两个map，一个保存目标串，一个保存窗口值String res = "";for(int i = 0;i<tc.length;i++){target.put(tc[i],target.getOrDefault(tc[i],0)+1);}int min = str.length;while(right<str.length){right++;if(right<str.length)map.put(str[right],map.getOrDefault(str[right],0)+1);while(isMatch()&&left<=right){if(min>=right-left+1){res = s.substring(left,right+1);min = right - left + 1;}map.put(str[left],map.getOrDefault(str[left],0)-1);left++;}}return res;}public boolean isMatch(){Set entry = target.entrySet();for(Object e : entry){Map.Entry o = (Map.Entry) e;Integer val = (Integer)o.getValue();Character key = (Character)o.getKey();if(map.getOrDefault(key,0)<val){return false;}}return true;}
}