leetcode 76 最小覆盖子串-蒲公英云

leetcode 76 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
说明：

如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路: 滑动窗口,设立2个即可，或者2个数组，但是这个处理的是匹配量的问题。维护匹配量，match变量来更高效处理问题。

这个版本的滑动窗口都是，全局的Map,通过设置变量i ,l 来判断区间，同时，维护min，来更新最小的串。

class Solution {
    public String minWindow(String s, String t) {
        String res = "";
        Map<Character,Integer> map = new HashMap<>();
        Map<Character,Integer> ma = new HashMap<>();
        for (char ti:t.toCharArray()) {
            map.put(ti,map.getOrDefault(ti,0)+1);
        }
        int min = Integer.MAX_VALUE;
        int l = 0;
        int i =0 ;
        int match = 0;
        while (l < s.length()) {
            char now = s.charAt(l);
            if (map.containsKey(now)) {
                if (ma.containsKey(now)) {
                    ma.put(now,ma.get(now)+1);
                } else {
                    ma.put(now,1);
                }
                if (ma.get(now).compareTo(map.get(now)) == 0) {
                    match++;
                }
            }
            l++;
            while(match == map.size()) {
                if (l - i < min) {
                    min = l-i;
                    res = s.substring(i,l);
                }
                char cc = s.charAt(i);
                if (map.containsKey(cc)) {
                    ma.put(cc,ma.get(cc)-1);
                    if (ma.get(cc) < map.get(cc))
                    match--;
                }
                i++;
            }
        }
        return res;
    }
}