题目: 最小覆盖子串
描述:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
方法一:滑动窗口
题目解读:该题与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> 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 &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()&&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 &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进行投诉反馈,一经查实,立即删除!