滑动窗口(8)_最小覆盖字串

个人主页：C++忠实粉丝
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝原创

滑动窗口(8)_最小覆盖字串

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌

1. 题目链接:

2. 题目描述 :

3. 解法 :

解法一(暴力枚举) + 哈希表 :

算法思路 :

代码展示 :

结果分析 :

对暴力算法的反思与优化 :

解法二(滑动窗口) :

算法思路 :

算法流程 :

代码展示 :

结果分析 :

4. 总结

1. 题目链接:

OJ链接:最小覆盖字串

2. 题目描述 :

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

注意：

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

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

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

提示：

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

3. 解法 :

解法一(暴力枚举) + 哈希表 :

算法思路 :

1. 用两层循环遍历整个数组

2. 用两个哈希表分别存储s和t的字符

3 当s的哈希表全部包含t哈希表中的数据,返回有效长度

4. 内层循环回退,外层循环++,进入下一层循环

5. 返回对有效长度取min的最后一个值即为我们所需的最小覆盖字串

代码展示 :

class Solution {bool check(int a[], int b[]){for(int i = 0; i < 128; i++)if(b[i] > a[i]) return false;return true;}
public:string minWindow(string s, string t) {int minlen = INT_MAX, left = 0;int hash1[128] = {0};int flag = 1;for(auto ch : t)hash1[ch]++;for(int i = 0; i < s.size(); i++){int hash2[128] = {0};for(int j = i; j < s.size(); j++){hash2[s[j]]++;if(check(hash2, hash1)) {flag = 0;if(j - i + 1 < minlen){minlen = j - i + 1;left = i;} break;}}}if(flag) return "";else return s.substr(left, minlen);}
};

结果分析 :

不出所料,由于题目中字符串s和t的长度达到了10^5,我们的暴力枚举时间复杂度为O(N^2),整体的数据级别达到了10^10,计算机无法在1s之内完成,会给出超出时间限制的错误

对暴力算法的反思与优化 :

1. check函数

我们其实可以发现我们的check函数在这道题中对我们的时间复杂度有很大的影响:
我们每比较一次就需要在check函数中遍历128次,所以我们的整体时间复杂度为128*10^10,这个就可以采用变量替换我们的check函数

2. 两层循环

我们能不能将两层循环优化成一层呢?不需要再让j移动一段距离后又重新回到i的位置,采用滑动窗口的方法,让[i,j]这个区间是合法区间

check函数优化

我们这里舍去了check函数,改用len和count统计:
len统计hash1中有效字符的数量

count统计hash2中有效字符的数量

注意:这里两个变量统计的是字符数量而不是个数是因为t字符可能会重复,比如:AAC

class Solution {public:string minWindow(string s, string t) {int minlen = INT_MAX, left = 0, len = 0;int hash1[128] = {0};int flag = 1;for(auto ch : t){if(hash1[ch] == 0) len++;hash1[ch]++;}for(int i = 0; i < s.size(); i++){int hash2[128] = {0}, count = 0;for(int j = i; j < s.size(); j++){hash2[s[j]]++;if(hash2[s[j]] == hash1[s[j]]) count++;if(count == len) {flag = 0;if(j - i + 1 < minlen){minlen = j - i + 1;left = i;} break;}}}if(flag) return "";else return s.substr(left, minlen);}
};

比之前多通过了一个例子,看来我们得优化还是有效果的

不过最后还是没能通过这道题主要是因为我们的暴力循环根本时间复杂度为O(N^2),这个改不掉的,所以接下来我们要对暴力算法的两层循环进行优化,将其优化成一层循环就能解决.

解法二(滑动窗口) :

算法思路 :

研究对象是连续的区间,因此可以尝试使用滑动窗口的思想来解决

如何判断当前窗口内的所有字符是符合要求的呢?

我们可以使用两个哈希表, 其中一个将目标串的信息统计起来,另一个哈希表的动态的维护窗口内字符串的信息.

当动态哈希表中包含目标串中所有的字符,并且对应的个数都不小于目标串的哈希表中各个字符的个数,那么当前窗口就是一种可行的方案

算法流程 :

1. 定义两个全局的哈希表: 1号哈希表hash1用来记录字串的信息,2号哈希表hash2用来记录目标串t的信息;

2. 实现一个接口函数,判断当前窗口是否满足要求:

遍历两个哈希表中对应的元素:

如果t中某个字符的数量大于窗口字符的数量,也就是2号哈希表某个位置大于1号哈希表.说明不匹配,返回false

如果全匹配返回true

代码展示 :

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = {0}, hash2[128] = {0};int len = 0, minlen = INT_MAX, begin = -1;for(auto ch : t)if(hash1[ch]++ == 0) len++;for(int left = 0, right = 0, count = 0; right < s.size(); right++){if(++hash2[s[right]] == hash1[s[right]]) count++;while(count == len){if(right - left + 1 < minlen){minlen = right - left + 1;begin = left;}if(hash2[s[left]]-- == hash1[s[left]]) count--;left++;}}return begin == -1 ? "" : s.substr(begin, minlen);}
};

结果分析 :

这段代码的时间复杂度分析如下：

初始化字符计数：遍历字符串 t，计算每个字符的频率，时间复杂度为
O(m)，其中m 是字符串 t 的长度。

双指针遍历字符串 s：

外层 for 循环遍历字符串 s，时间复杂度为O(n)其中n 是字符串 s 的长度。
内层 while 循环在最坏情况下会遍历字符串 s，但由于 left 和 right 只会各自移动一次，因此总体上 while 循环也可以认为是O(n)

综合以上分析，整体的时间复杂度为：
O(m + n)

这里m 是字符串 t 的长度，n 是字符串 s 的长度。这个复杂度是非常高效的，适合处理较大的输入。