LeetCode76 最小覆盖子串

发表于 | 分类于 |
字数统计: 441 | 阅读时长 ≈ 1

链接：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;
}