leetcode76-最小覆盖子串

原题

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

示例:

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明:

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

解法

思想

滑动窗口,用一个hashmap存储原字符串中字符的出现个数,再用一个hashmap存储滑动窗口内目标字符的出现个数,用一个变量记录滑动窗口内有多少个字符满足条件了。

代码

class Solution {
    public String minWindow(String s, String t) {
        int left = 0, right = 0;
        int start = 0, end = Integer.MAX_VALUE;
        Map<Character, Integer> window = new HashMap();
        Map<Character, Integer> needMap = new HashMap();
        for(int i = 0; i < t.length(); i++) {
            needMap.put(t.charAt(i), needMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int match = 0;
        while(right < s.length()) {
            char rightTemp = s.charAt(right);
            if(needMap.containsKey(rightTemp)) {
                int newCount = window.getOrDefault(rightTemp, 0) + 1;
                window.put(rightTemp, newCount);
                if(newCount == needMap.getOrDefault(rightTemp, 0)){
                    match++;
                }
            }
            right++;
            while(match == needMap.size()) {
                if(right - left < end - start) {
                    start = left;
                    end = right;
                }
                char leftTemp = s.charAt(left);
                if(needMap.containsKey(leftTemp)) {
                    window.put(leftTemp, window.getOrDefault(leftTemp, 0) - 1);
                    if(window.getOrDefault(leftTemp, 0) < needMap.getOrDefault(leftTemp, 0)) {
                        match--;
                    }
                }
                left++;
            }
        }
        return end == Integer.MAX_VALUE ? "" : s.substring(start, end);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode76-%e6%9c%80%e5%b0%8f%e8%a6%86%e7%9b%96%e5%ad%90%e4%b8%b2/