LeetCode 76. 最小覆盖子串

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析

通过题意可知，我们要从s字符串中找到包含t字符串的最小子串，因此我们可以通过哈希的方式来计算字符串中含有字符的次数和种类映射。定义两个哈希表，一个用来映射s字符串，一个用来映射t字符串。遍历s字符串并且记录遍历的字符以及出现次数，当该字符出现的次数等于t字符时，说明该字符已经符合条件，然后定义一个变量来记录。每有一个符合条件就count++;当count与t字符中的种类数相等时，当前子串就是s的覆盖子串了。

细节处理

如果此时s中不含有t的子串，返回-1；

代码

class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        int ns=s.size();
        int nt=t.size();
 
        int s_hash[128]={0};
        int t_hash[128]={0};
        // kinds用来计算t字符串中字符的种类
        int kinds=0;
        for(auto&ch:t) 
        {
            if(t_hash[ch]==0) kinds++;
            t_hash[ch]++;
        }
        // 使用minlen来记录答案
        int minlen=INT_MAX;
        // begin来记录每次截取子串的起始位置
        int begin=-1;
        for(int left=0,right=0,count=0;right
        {
            // 进窗口
            char in=s[right];
            if(++s_hash[in]==t_hash[in]) count++;
            // 切记一定要先更新结果再出窗口
            // 因为出窗口之后count==kinds的条件可能就不成立了
            while(count==kinds)
            {
                // 更新结果
                if(right-left+1
                {
                    minlen=right-left+1;
                    begin=left;
                }
                // 出窗口
                char out=s[left++];
                if(s_hash[out]--==t_hash[out]) count--;
            }
 
        }
        // begin==-1说明根本就没有进入while循环
        // 也说明了根本就不存在count==kinds这个条件
        // 因此没有符合条件的答案
        if(begin==-1) return "";
        // 截取最小覆盖子串以begin为起始位置，截取minlen个长度
        return s.substr(begin,minlen);
    }
};