本文介绍: 该题与32题(详细见上一篇讲解32串联所有单词子串)很相似,唯一不同的是本题所求子串中不仅包含t中的所有字符,还可以包含其他的字符,因此所求子串和t是一个包含的关系,而32题所求子串和t的字符是一一对应的,没有多余的字符,即子串的长度等于t的长度,而此题子串的长度大于等于t的长度。发现此时窗口不包含t中的所有元素,那么right指针右移,此时窗口包含t中所有的元素记录此时的子串长度。过程如图所示,阴影部分为当前窗口,其中红色字体的字母为存储哈希表中的元素,窗口内其它元素不进行存储

题目: 最小覆盖子串

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

注意:

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

示例 1:

输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

leetcode链接

方法一:滑动窗口
题目解读:该题与32题(详细见上一篇讲解32串联所有单词的子串)很相似,唯一不同的是本题所求子串中不仅包含t中的所有字符,还可以包含其他的字符,因此所求子串和t是一个包含的关系,而32题所求子串和t的字符是一一对应的,没有多余的字符,即子串的长度等于t的长度,而此题子串的长度大于等于t的长度。
求解:同样的我们利用32题的滑动窗口的方法过程完全一致,唯一不同该题的窗口为动态长度的,即定义一个窗口,初始长度为0,然后判断当前窗口是否包含t中所有的字符,如果包含,那么记录该窗口的长度并且维护一个最小的满足条件的窗口长度,并且left指针右移,即缩小窗口的长度。如果不包含t中所有字符,那么right指针右移,即增大窗口,循序以上操作
那么我们如何判断窗口是否包含t中的所有字符呢,我们考虑最佳时间复杂度的做法,即为定义2个unordered_map,分别为map1和map2,map1记录中字母的出现次数,map2记录窗口字母的出现次数,然后判断map1和map2,如果map1中所有的关键字的值都小于等于map2,那么可以认为窗口包含了t中所有字符。这里存储map2的时候,只需要存储在map1中出现过的关键字,含义即为只存储t中出现过的字符到map中,这样做节省空间的消耗。
时间复杂度:o(Cn,+m) 时间包括指针的移动(窗口的枚举),为o(n),和判断窗口是否包含t中字符的时间,即为哈希表的查询,设哈希表的大小为C,那么时间复杂度为o(Cn),还有初始把t中所有字符插入哈希表的时间,为o(m),所以总时间复杂度为o(Cn+m)。

过程如图所示,阴影部分为当前窗口,其中红色字体的字母为存储哈希表中的元素,窗口内其它元素不进行存储
在这里插入图片描述

发现此时窗口不包含t中的所有元素,那么right指针右移,此时窗口包含t中所有的元素,记录此时的子串长度
在这里插入图片描述
然后left指针右移
在这里插入图片描述

class Solution {
public:
    unordered_map<char,int&gt; smap,tmap;

    string minWindow(string s, string t) {
        int n = s.size(),m = t.size();
        int len = INT_MAX, ansL = -1, ansR = -1;
        for(auto &amp;c : t){
            tmap[c]++;//存储t中单词出现的次数
        }
        int left = 0,right = -1;
        while(right<n){
        	//窗口右移
            if(tmap.find(s[++right])!=tmap.end()){//统计在t中出现过的字符的个数
                smap[s[right]]++;
            }
            while(check()&amp;&amp;left<=right){//如果窗口中包含s所有字符,那么left指针右边移
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    ansL = left;
                }
                if(tmap.find(s[left])!=tmap.end()){
                    smap[s[left]]--;
                }
                left++;
            }
        }
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
    bool check(){
        for(auto &amp;p:tmap){
            if(smap[p.first]<p.second){
                return false;
            }
        }
        return true;
    }
};

原文地址:https://blog.csdn.net/weixin_48144140/article/details/134662510

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_5003.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注