☆打卡算法☆LeetCode 76、最小覆盖子串 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定两个字符串st，返回字符串s中覆盖t所有字符的最小子串。”

题目链接：

来源：力扣（LeetCode）

链接：76. 最小覆盖子串 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

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

示例 2：
输入： s = "a", t = "a"
输出： "a"

二、解题

1、思路分析

哈哈 经典滑动窗口的题目。

题意要求返回字符串s中覆盖t全部字符的最小子串，可以将包含t的子串的看做可行窗口。

在滑动窗口中会有两个指针，一个用于延伸现有窗口的指针，一个用于收缩窗口的指针。

那如果判断当前串口包含所有t所需的字符呢？可以用一个哈希表来表示t中所有的字符及数量。

如果这个哈希表中的对应的个数都不小于t的哈希表中各个字符的个数，那么当前窗口是可行的。

2、代码实现

代码参考：

public class Solution
{
    
    Dictionary<char, int> sDic = new Dictionary<char, int>();
    Dictionary<char, int> tDic = new Dictionary<char, int>();
    public string MinWindow(string s, string t)
    {
sDic.Clear();
        tDic.Clear();
        //考虑t中有相同字符的情况，所以需要统计t中每个字符的出现次数
        for (var i = 0; i < t.Length; i++)
        {
            AddItem(tDic, t[i]);
        }

        var left = 0;
        var right = 0;
        int areaL =0;
        int ansL = s.Length+1;
        while (right < s.Length)
        {           
            if (right<s.Length&& tDic.ContainsKey(s[right]))
            {
                AddItem(sDic, s[right]);
            }
            while (CheckDic() && left <= right)
            {
                if (ansL> right-left+1)
                {
                    ansL = right - left + 1;
                    areaL = left;
                }                
                RemoveItem(sDic, s[left]);
                left++;
            }
            right++;
        }
        if (ansL > s.Length) return "";
        return s.Substring(areaL, ansL);
    }
    void AddItem(Dictionary<char, int> dic, char key)
    {
        if (dic.ContainsKey(key))
        {
            dic[key]++;
        }
        else
        {
            dic.Add(key, 1);
        }
    }
    void RemoveItem(Dictionary<char, int> dic, char key)
    {
        if (dic.ContainsKey(key))
        {
            dic[key]--;
        }
    }
    bool CheckDic()
    {
        foreach (var i in tDic)
        {
            if (sDic.ContainsKey(i.Key))
            {
                if (sDic[i.Key] < tDic[i.Key])
                {
                    return false;
                }
            }
            else
            {

                return false;
            }
        }
        return true;
    }

}

3、时间复杂度

时间复杂度 ： O(n)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

先考虑从左到右，找到t中第一个相同的字符，然后将字符存入_matchList及state，然后往下找。

当出现相同的时候存入state，再看_matchList中有没有,没有就加入，有就看是否==s[_maxLeft]，否就跳过

是就找到最左侧不为空的state，并将_maxLeft=index。然后用类似的方式考虑从右到左。

最后看_matchList的长度是否与t一致，一样就提取s中_maxLeft到_maxRight的字符串。

BUG：忘记处理从右往左时，最右侧与最左侧相同的情况，于是换思路：看题解，看了滑动窗口的原理。

字典查找消耗很大，还是用hashmap会好一些