76.最小覆盖子串.md

方法一：滑动窗口（暴力）

class Solution {
    public String minWindow(String s, String t) {
        String res = "";
        int[] cnt = new int[58];
        for (Character ch : t.toCharArray()) {
            cnt[ch - 'A']++;
        }
        for (int i = 0; i < s.length(); i++) {
            int[] tmp = new int[58];
            for (int j = i; j < s.length(); j++) {
                tmp[s.charAt(j) - 'A']++;
                if (isMatch(cnt, tmp) && (res == "" || (j - i + 1) < res.length())) {
                    res = s.substring(i, j + 1);
                    break;
                }
            }
        }
        return res;
    }

    public boolean isMatch(int[] cnt, int[] tmp) {
        for (int i = 0; i < 58; i++) {
            if (tmp[i] < cnt[i]) return false;
        }
        return true;
    }
}

方法二：滑动窗口

假设要查找的字符串是"ABC"，s中为“XXXABCXXX"。当滑动窗口的右指针扫到C时可以匹配，记录当前滑动窗口的左右端点及长度。将滑动窗口的左指针不断右移跳过XXX，从而提高效率。

class Solution {
    public String minWindow(String s, String t) {
        int[] cnt = new int[58]; // (A ~ z) 之间有58个数，A的ASCII码z
        for (Character ch : t.toCharArray()) {
            cnt[ch - 'A']++;
        }
        int left = 0, right = -1, ansLeft = -1, ansRight = -1;
        int[] tmp = new int[58];
        int len = Integer.MAX_VALUE;
        while (right < s.length()) {
            right++;
            if (right < s.length()) {
                tmp[s.charAt(right) - 'A']++;
            }
            while (isMatch(cnt, tmp) && left <= right) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    ansLeft = left;
                    ansRight = left + len;
                }
                tmp[s.charAt(left) - 'A']--;
                left++;
            }
        }
        return ansLeft == -1 ? "" : s.substring(ansLeft, ansRight);
    }

    public boolean isMatch(int[] cnt, int[] tmp) {
        for (int i = 0; i < 58; i++) {
            if (tmp[i] < cnt[i]) return false;
        }
        return true;
    }
}