LeetCode每日一题5月23日 LeetCode76.最小覆盖字串

绝地灬酷狼 2023-02-11 10:22 4阅读 0赞

## 问题描述： ##

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/minimum-window-substring][https_leetcode-cn.com_problems_minimum-window-substring]

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
    输出: "BANC"
    说明：
    
    如果 S 中不存这样的子串，则返回空字符串 ""。
    如果 S 中存在这样的子串，我们保证它是唯一的答案。

## 解题思路： ##

使用**滑动窗口思想，**

**开辟俩个map结构，一个用来存储字符串T中的字符**

for(char c:t){
                need[c]++;
            }

**一个用来存储窗口window中的字符，从头开始遍历，当window\[c\]==need\[c\]时，match++**

**match==need.size()时  更新长度**

class Solution {
    public:
        string minWindow(string s, string t) {
            if(s.size()<t.size()) return "";
            int start = 0,minlen = INT_MAX;
            map<char,int> need;
            map<char,int> window;
            for(char c:t){
                need[c]++;
            }
            int match = 0;
            int left=0,right=0;
            while(right<s.size()){
                char c1 = s[right];
                if(need.count(c1)){
                    window[c1]++;
                    if(window[c1]==need[c1]){
                        match++;
                    }
                }
                right++;
                while(match==need.size()){
                    if(right-left<minlen){
                        minlen = right-left;
                        start =  left;
                    }
                    char c2 = s[left];
                    if(need.count(c2)){
                        window[c2]--;
                        if(window[c2]<need[c2]){
                            match--;
                        }
                    }
                    left++;
                }
            }
            return minlen == INT_MAX ?  "":s.substr(start,minlen);
        }
    };

[https_leetcode-cn.com_problems_minimum-window-substring]: https://leetcode-cn.com/problems/minimum-window-substring