Leetcode 76. 最小覆盖子串(滑动窗口算法 YYDS)

àì夳堔傛蜴生んèń 2022-08-31 12:23 134阅读 0赞

#### 题目重述 ####

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

##### 注意： #####

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。  
如果 s 中存在这样的子串，我们保证它是唯一的答案。

#### 示例 1： ####

输入：s = “ADOBECODEBANC”, t = “ABC”  
输出：“BANC”

#### 示例 2： ####

输入：s = “a”, t = “a”  
输出：“a”

#### 示例 3: ####

输入: s = “a”, t = “aa”  
输出: “”  
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，  
因此没有符合条件的子字符串，返回空字符串。

#### 提示： ####

1 <= s.length, t.length <= 105  
s 和 t 由英文字母组成

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/minimum-window-substring  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

本题的思想是使用滑动窗口算法，需要注意题目中条件是“涵盖 t 所有字符”

滑动窗口的思路并不难：

*  初始化左右指针，一个窗口(Map)、一个need(Map)，窗口用于保存当前窗口的元素及次数，need是当前需要的字符及对应次数，初始化时操作
 *  扩张阶段：移动right，不断扩张窗口
 *  缩减阶段：当窗口中的子串已经满足本题条件，那么就是找最小，即移动left，不断缩小窗口

#### Java实现 ####

//leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        
    //    测试用例:"ADOBECODEBANC"
    //            "ABC"
    //    测试结果:"ANC"
    //    期望结果:"BANC"
        private Map<Character,Integer> need,window;
        public String minWindow(String s, String t) {
        
            if (s == null || s.length() == 0 || t == null || t.length() == 0){
        
                return "";
            }
            // 暂时需要的各元素的数量
            need = new HashMap<>();
            window = new HashMap<>();
            // 记录最小覆盖子串的长度、起始索引
            int minLen = Integer.MAX_VALUE,start = 0;
            // 左右指针
            int left = 0,right = 0;
            // window中满足need条件的字符个数
            int valid = 0;
            // 初始化条件要求的字符
            for (int i = 0; i < t.length(); i++) {
        
                // 次数为1，代表是需要的个数
                need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1);
            }
            while(right<s.length())
            {
        
                // c 是将移⼊窗⼝的字符
                char c = s.charAt(right);
                // 右移窗⼝
                right++;
                // 把数据加入窗口,即出现次数+1
                window.put(c,window.getOrDefault(c,0)+1);
                // 进⾏窗⼝内数据的⼀系列更新
                if (need.containsKey(c)) {
        
                    if (window.get(c).intValue() == need.get(c).intValue()) {
        
                        valid++;
                    }
                }
                // 判断左侧窗⼝是否要收缩,收缩条件是已经满足
                while (valid == need.size()) {
        
                    // 在这⾥更新最⼩覆盖⼦串
                    if (right - left < minLen) {
        
                        start = left;
                        minLen = right - left;
                    }
                    // d 是将移出窗⼝的字符
                    char d = s.charAt(left);
                    // 左移窗⼝
                    left++;
                    // 进⾏窗⼝内数据的⼀系列更新
                    if (need.containsKey(d)) {
        
                        if (window.get(d).intValue() == need.get(d).intValue()) {
        
                            valid--;
                        }
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
            return minLen == Integer.MAX_VALUE? "":s.substring(start,start+minLen);
        }
    }