文章目录
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例
示例一
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例二
输入：s = "a", t = "a"
输出："a"
示例三
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
解题思路
这时一道非常经典的滑动窗口题目，所以我们可以采用双指针+双窗口的解法。假设现在两个字符串的状态如下：
我们新建两个窗口window和need。其中need窗口用于记录每个记录需要匹配几次；window窗口则用于记录当前滑动窗口期中每个字符出现的次数，所以这两个变量我们都可以用unordered_map。此时，我们建立滑动窗口，让left和right都指向字符串S的起始。
此时我们把right指针往右移一步，此时字符A就被添加到了Window窗口之中。
之后，我们不断迭代这个过程，直到我们Window窗口中的字符出现满足need窗口中每个字符出现的个数。
这个时候我们就拿到第一个匹配的子串"ADOBEC"，我们可以开始尝试收缩左边界了，一直收缩到Window窗口不满足need窗口。
收缩完之后，我们继续刚刚找子串的过程，这个时候我们会找到第二个 “满足条件” 的子串。
可以看到这个子串有点多余，所以我们收缩左边界，得到第二个满足条件的子串"CODEBA"
之后再次迭代，直到终止条件right出字符串S的边界，最后比对我们找到满足条件的子串中长度的最小值就可以了。这个案例中是"BANC"。
代码呈现
class Solution {
public:
/**
* @brief leetcode 提供的函数
*
* @param s 被匹配的字符串
* @param t 待匹配的字符串
* @return string 最小覆盖子串
*/
string minWindow(string s, string t) {
unordered_map<char, int> need; //需要凑齐的子串
unordered_map<char, int> window; //窗口中的字符
//记录待匹配的字符中每个字符出现的次数
for (char c : t) {
need[c]++;
}
int left = 0; //左边界
int right = 0; //右边界
int valid = 0; //记录匹配上的字符数
int str_start = 0; // s字符串起始的位置
int len = INT32_MAX;
int s_size = s.size();
while (right < s_size) {
char ch = s[right];
right++;
if (need.count(ch)) {
window[ch]++;
if (window[ch] == need[ch]) {
//一个字符完全匹配上了
valid++;
}
}
//判断左侧窗口是否需要收缩
while (valid == need.size()) {
if (right - left < len) {
str_start = left;
len = right - left;
}
//移出字符
char delete_ch = s[left];
left++;
if (need.count(delete_ch)) {
if (window[delete_ch] == need[delete_ch]) {
valid--;
}
window[delete_ch]--;
}
}
}
return len == INT32_MAX ? "" : s.substr(str_start, len);
}
};
参考文献
[1] labuladong的算法小抄[M].付东来