Luobuyu's Blog

0%

76.最小覆盖子串

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.1k 阅读时长 ≈ 1 分钟
使用滑动窗口解决，注意判断当前窗口是否包含了所有字符。

76.最小覆盖子串

题目描述：

给出字符串s和t，长度分别为 $ m,n $ 。返回s中包含t的所有字符（包括个数）的最小子串。如果不存在返回空。注意t中可能有重复字符。

数据范围：
$ 1\le m, n \le 10^5 $

题解：

直接使用滑动窗口。首先记录一下t中字符的频次，使用哈希表记录，同时使用一个变量记录总共有多少个字符。这样的话就可以方便的统计当前窗口还缺几个。（不能记录种类，因为t中有重复字符）

滑动窗口，right移动，遇到t中的字符，哈希表频次减减，如果频次大于 $ 0 $ ，tmp--，说明缺少的字符个数减少了 $ 1 $ 。等到 tmp = 0时，移动左窗口，如果某个字符的频次大于 $ 0 $ 说明缺少该字符。

使用该 tmp 变量可以避免再使用一个哈希表记录当前窗口都有什么字符。

s.substr(begin, size)注意第二个参数是长度，不是end

代码：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    unordered_map<char, int> mp;
    string minWindow(string s, string t)
    {
        for (int i = 0; i < t.size(); ++i)
        {
            mp[t[i]]++;
        }
        int tmp = t.size(); // 窗口中缺少的个数
        int left = 0;
        int ans = INF, l = -1, r = -1;
        for (int right = 0; right < s.size(); ++right)
        {
            if (mp.count(s[right]))
            {
                if (mp[s[right]] > 0)
                {
                    tmp--;
                }
                mp[s[right]]--;
            }
            while (tmp == 0)
            {
                if (ans > right - left + 1)
                {
                    ans = right - left + 1;
                    l = left;
                    r = right;
                }
                if (mp.count(s[left]))
                {
                    mp[s[left]]++;
                    if (mp[s[left]] > 0)
                    {
                        tmp++;
                    }
                }
                left++;
            }
        }
        if (ans == INF)
            return "";
        else
            return s.substr(l, ans);
    }
};