Leetcode76. 最小覆盖子串

题目描述

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

**注意：**如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

1
2
输入：s = "a", t = "a"
输出："a"

提示：

  • 1≤s.length,t.length≤1051 \leq s.length, t.length \leq 10^5
  • s 和 t 由英文字母组成

**进阶：**你能设计一个在 o(n) 时间内解决此问题的算法吗？

解题思路

这道题要求给出时间复杂度为O(n)O(n)的算法，我们考虑用滑动窗口算法去解决。

思路如下：用两个指针分别指示窗口的边界，记为i和j，先向右滑动j指针，使得窗口内的字符串包含了字符串t，然后记录下起始下标start和长度minLen进行后续的比较。然后，接着向右滑动i指针，指针窗口内的字符串恰好刚刚不包含字符串t，再滑动指针j。循环往复，直至遍历完字符串s，得到最终答案。

这里面需要解决一个问题：

如何判断窗口内的字符串已经包含字符串t？

我们首先初始化一个哈希表为字符串t中每一个字符出现的次数。这些初始化的字符次数都为正数，也就是表示了对于每一个字符我们还需要多少个。这样的话，在遍历字符串s中的字符的时候，对于出现的每一个字符我们将它在哈希表中减1(如果这个字符之前就在哈希表中，那么就在原来的次数上减1，否则先在哈希表中将这个字符的次数初始化为0，再减去1)，这样的话，次数就有可能为负数，这就表示这个字符我们多余了多少个。

可以用stl中的哈希表，但是比较慢，推荐使用int类型的vector，初始化为128 个长度，初始值为0，这样就可以用ASCII码来表示字符了，这样的哈希表速度更快。

使用哈希表后，其实我们已经可以实现这个功能了，比如：遍历哈希表，将每个次数大于0的字符的次数加起来，就是我们总共在窗口中还需要包含的字符的个数，当它为0的时候说明就已经全部包含了。再进行优化，直接用一个变量totalCount来表示这个总和，在过程中进行更新就可以了。

PS: 需要注意编码过程中的边界条件！

具体细节可以参考示例代码：

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
string minWindow(string s, string t)
{
    unordered_map<char,int>mp;
    int totalCount=0;
    for(int i=0;i<t.size();++i)
    {
        mp[t[i]]++;
        totalCount++;
    }

    int i=0,j=0;
    int start=0;
    int minLen=INT32_MAX;
    while (j<=s.size())
    {
        while(totalCount==0)
        {
            if(j-i<minLen)
            {
                minLen=j-i;
                start=i;
            }
            mp[s[i]]++;
            if(mp[s[i]]>0)
            {
                totalCount++;
            }       
            i++;
        }
        if(mp[s[j]]>0)
        {     
            totalCount--;
        }
        mp[s[j]]--;
        j++;
    }
    string ans=minLen==INT32_MAX?"":s.substr(start,minLen);
    return ans;  
}
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
string minWindow(string s, string t)
{
    vector<int>mp(128,0);
    int totalCount=0;
    for(int i=0;i<t.size();++i)
    {
        mp[t[i]]++;
        totalCount++;
    }

    int i=0,j=0;
    int minLen=INT32_MAX;
    string ans="";
    while (j<=s.size())
    {
        while(totalCount==0)
        {
            if(j-i<minLen)
            {
                minLen=j-i;
                ans=s.substr(i,minLen);
            }
            mp[s[i]]++;
            if(mp[s[i]]>0)
            {
                totalCount++;
            }       
            i++;
        }
        if(mp[s[j]]>0)
        {     
            totalCount--;
        }
        mp[s[j]]--;
        j++;
    }
    return ans;  
}

时间复杂度为：O(n)O(n)，nn为字符串s的长度

空间复杂度为：o(m)o(m)，mm为字符串t的长度