Leetcode76. 最小覆盖子串

2021年5月27日 451点热度 2人点赞 1条评论

题目描述

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

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

示例 1:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"

示例 2:

输入:s = "a", t = "a"
输出:"a"

提示:

  • $1 \leq s.length, t.length \leq 10^5$
  • st 由英文字母组成

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

解题思路

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

思路如下:用两个指针分别指示窗口的边界,记为ij,先向右滑动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: 需要注意编码过程中的边界条件!

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

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;  
}
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)$,$n$为字符串s的长度

空间复杂度为:$o(m)$,$m$为字符串t的长度

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

  • 乐乐

    最小的覆盆子串串🍓🍓

    2021年5月27日