12.最小覆盖字串

raylan.chen大约 4 分钟

class Solution {
    public String minWindow(String S, String t) {
        char[] s = S.toCharArray();
        int m = s.length;
        int ansLeft = -1;
        int ansRight = m;
        int[] cntS = new int[128]; // s 子串字母的出现次数
        int[] cntT = new int[128]; // t 中字母的出现次数
        for (char c : t.toCharArray()) {
            cntT[c]++;
        }

        int left = 0;
        for (int right = 0; right < m; right++) { // 移动子串右端点
            cntS[s[right]]++; // 右端点字母移入子串
            while (isCovered(cntS, cntT)) { // 涵盖
                if (right - left < ansRight - ansLeft) { // 找到更短的子串
                    ansLeft = left; // 记录此时的左右端点
                    ansRight = right;
                }
                cntS[s[left]]--; // 左端点字母移出子串
                left++;
            }
        }
        return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
    }

    private boolean isCovered(int[] cntS, int[] cntT) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        return true;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-window-substring/solutions/2713911/liang-chong-fang-fa-cong-o52mn-dao-omnfu-3ezz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人理解：

使用两个长度为128（ASCII 表字符个数）int 数组 cntS、cntT 存储字符串 s、t 中字符出现过的次数（相当于哈希表，key 为数组索引下标）；

统计字符串 t 中字符出现次数；

使用「滑动窗口」遍历字符串 s ，滑动窗口右边界每右移一次，cntS[滑动窗口新增字符]++，并且验证 cntS 中 'A' ~ 'Z'、'a'~'z' 中的值是否大于等于 cntT，符合条件则滑动窗口左边界右移，并持续判断缩小后的滑动窗口能否满足问题要求。

另外，对于滑动窗口「左边界右移」每次都需要重新判断 cntS 数组 'A' ~ 'Z'、'a'~'z' 中的值是否大于等于 cntT，可简化为：只判断右移后舍弃掉的字符在数组 cntS、cntT 中的值，当 cntS[舍弃字符] < cntT[舍弃字符] 退出循环即可。

class Solution {
    public String minWindow(String s, String t) {
        // 滑动窗口
        if (s.length() < t.length()) return "";
        // 数组T存储字符串T中字符出现次数
        // 128个ASCII码
        int[] arrT = new int[128];
        // 遍历字符串S
        for (int i = 0; i < t.length(); i++) {
            arrT[t.charAt(i)]++;
        }
        // 数组S存储字符串S中字符出现次数
        int[] arrS = new int[128];
        // 滑动窗口，左右边界
        int winLeft = -1; int winRig = s.length();
        // 遍历过程中，每向右移动一次检测是否与数组T匹配
        for (int i = 0, j = 0; j < s.length(); j++) {
            arrS[s.charAt(j)]++;
            // 匹配则尝试移动左边界，试图寻找满足条件 滑动窗口的最小值
            if (compare(arrS, arrT)) {
                boolean flag = true;
                while (flag) {
                    if (winRig - winLeft > j - i) {
                        winLeft = i;
                        winRig = j;
                    }
                    char tmp = s.charAt(i);
                    arrS[s.charAt(i)]--;
                    if (arrS[tmp] < arrT[tmp]) flag = false;
                    i++;
                }
            }
        }
        if(winLeft < 0) return "";
        else return s.substring(winLeft, winRig + 1);
    }

    /**
     * 匹配函数
     */
     public boolean compare(int[] arrS, int[] arrT) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (arrS[i] < arrT[i]) return false;
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (arrS[i] < arrT[i]) return false;
        }
        return true;
     }
}

还可进一步简化：

遍历字符串 s，「滑动窗口右边界右移」时，判断滑动窗口中的字符是否与字符串 t 匹配；

滑动窗口右边界右移过程中，cnt[右边界新增字符]--，cnt 此时代表字符串 t 中字符 c 相比滑动窗口中字符 c 多出现了 cnt[c] 次；

并借助变量 less 记录「字符串 t 与滑动窗口相比多了 less 种字符」；

cnt 数组记录单个字符相差程度，less 记录整个字符串相差程度。

class Solution {
    public String minWindow(String S, String t) {
        char[] s = S.toCharArray();
        int m = s.length;
        int ansLeft = -1;
        int ansRight = m;
        int[] cnt = new int[128];
        int less = 0;
        for (char c : t.toCharArray()) {
            if (cnt[c] == 0) {
                less++; // 有 less 种字母的出现次数 < t 中的字母出现次数
            }
            cnt[c]++;
        }

        int left = 0;
        for (int right = 0; right < m; right++) { // 移动子串右端点
            char c = s[right]; // 右端点字母
            cnt[c]--; // 右端点字母移入子串
            if (cnt[c] == 0) { 
                // 原来窗口内 c 的出现次数比 t 的少，现在一样多
                less--;
            }
            while (less == 0) { // 涵盖：所有字母的出现次数都是 >=
                if (right - left < ansRight - ansLeft) { // 找到更短的子串
                    ansLeft = left; // 记录此时的左右端点
                    ansRight = right;
                }
                char x = s[left]; // 左端点字母
                if (cnt[x] == 0) {
                    // x 移出窗口之前，检查出现次数，
                    // 如果窗口内 x 的出现次数和 t 一样，
                    // 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少
                    less++;
                }
                cnt[x]++; // 左端点字母移出子串
                left++;
            }
        }
        return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-window-substring/solutions/2713911/liang-chong-fang-fa-cong-o52mn-dao-omnfu-3ezz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

12.最小覆盖字串

12.最小覆盖字串

参考链接

优秀题解