题目描述

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

样例

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

输入：s = "AAOBECODEBANC", t = "AAC"
输出："AOBECODEBANC"

输入：s = "AEODEBNC", t = "ABC"
输出："AEODEBNC"

算法1

(暴力枚举) $O(C⋅∣s∣+∣t∣)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> need,window;
        //need中存t串中字符的个数
        for(char c:t) need[c]++;
        int vaild=0;
        int left = 0;
        int right = 0;
        int len = s.size();
        int start = 0;
        bool tag = false;
        //window放s串的一部分，left,right为s中左右边界指针
        //直到窗口滑动到s的最右端，才停止
        while(right<s.size())
        {
            //扩大窗口
            char a = s[right++];
            if(need[a]>0)
            {
                window[a]++;
                if(window[a]<=need[a]) vaild++;
            }
            //当找到一个可行解，则收缩窗口（向右移动）
            //两个目的：1优化可行解，让左边界向右收缩，长度更短
            //2.离开当前可行解，好寻找下一个可行解
            while(vaild==t.size())
            {
                tag = true;
                //记录长度更短的解的起始下标和长度
                if(len>right-left)
                {
                    start = left;
                    len = right-left;
                }
                char b = s[left++];
                if(need[b]>0)
                {
                    window[b]--;
                    if(window[b]<need[b]) vaild--;
                }
            }
        }
        //cout<<vaild<<":"<<t.size()<<endl;
        if(!tag) return "";
        string res="";
        for(int i=start;i<start+len;i++) res+=s[i];
        return res;

    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla