题目解析

76. 最小覆盖子串


本题将意思转换一下：寻找最小可重复字符的字串

算法讲解

使用滑动窗口+哈希表，进行入窗口->判断哈希表中的元素是否符合最小可重复子串的条件->出窗口

class Solution {
public:
    //检查两个hash表中的字符
    bool check(int* hash_s, int* hash_t)
    {
        //注意t当中可能包含相同字符
        for(int i = 0; i < 128; i++)
        {
            if(hash_s[i] < hash_t[i])return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        int hash_s[128] = {0};
        int hash_t[128] = {0};
        string ret;
        int len = INT_MAX;
        int left = 0, right = 0;
        int begin = -1; //记录最小字串的起始位置
        //填充hash_t
        for(auto ch : t) hash_t[ch]++;
        while(right < s.size())
        {
        	//入窗口
            hash_s[s[right]]++;
            //检查当前的hash是否符合字串条件
            while(check(hash_s, hash_t))
            {
                if (min(len, right - left + 1) != len)
                {
                    len = min(len, right - left + 1);
                    begin = left;
                }
                //出窗口
                hash_s[s[left++]]--;
            }
            //移动窗口
            right++;
        }
        if(begin == -1)return "";
        return s.substr(begin, len);
    }
};