LeetCode76 最小覆盖子串

链接:https://leetcode-cn.com/problems/minimum-window-substring/

题面

给定两个字符串 s 和 t,求 s 中包含 t 所有字符的最短连续子字符串的长度。这里要注意,不仅是要求包含t中所有的字符,其字符的数量也需要满足。

解法

这道题需要用到滑动窗口的解法,但是在实现方面有一些trick。
题解中的写法我认为十分巧妙,从中学到了不少技巧,故作记录。
用两个数组chars[]和 flag[]分别表示当前还需要的某个字符的数量以及这个字符是否在t中出现
并用一个变量count去记录当前的字符个数
这个做法巧妙的地方在于当chars[]中某个字符的数值小于0的时候,我们就知道这个字符的数量已经够了(覆盖了t中出现的所有字符),所以此时可以不用再增加count值。
当count值大小达到t的长度时,窗口的左端点向左滑动,这里还是一样用chars[]去判断这个字符被去掉以后是否仍满足覆盖t中所有字符(太妙了)
还有一个小技巧,滑动的时候用while替代if,精简代码中循环的数量

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
string minWindow(string s, string t)
{
string ans = "";
vector<int> chars(200);
vector<bool> flag(200);
for (char ch : t) {
chars[ch]++;
flag[ch] = 1;
}
int l = 0, count = 0, minlen = s.size() + 1;
for (int r = 0; r < s.size(); r++) {
if (flag[s[r]]) {
if (--chars[s[r]] >= 0) {
count++;
}
while(count == t.size()) {
if (r - l + 1 < minlen) {
minlen = r - l + 1;
ans = s.substr(l, minlen);
}
if (flag[s[l]] && ++chars[s[l]] > 0) {
count--;
}
l++;
}
}
}
return ans;
}