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

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

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

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&amp;&amp; tDic.ContainsKey(s[right]))
            {
                AddItem(sDic, s[right]);
            }
            while (CheckDic() &amp;&amp; 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;
    }

}