76最小覆盖子串

系统管理员 2023-03-01 11:54 2阅读 0赞

## 一、前言 ##

标签：字符串滑动窗口。

问题来源LeetCode 76 难度：困难。

问题链接：[https://leetcode-cn.com/problems/minimum-window-substring/][https_leetcode-cn.com_problems_minimum-window-substring]

## 二、题目 ##

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

**示例：**

输入: S = "ADOBECODEBANC", T = "ABC"
    输出: "BANC"

**说明：**

*  如果 S 中不存这样的子串，则返回空字符串 ""。
 *  如果 S 中存在这样的子串，我们保证它是唯一的答案。

## 三、思路 ##

字符串且还包含有子串需要想到用滑动窗口，本题用滑动窗口解决。在滑动过程中（也就是窗口头是添加，窗口尾是删除）需要确定字符是否属于子串中，下面解题中用了一种很巧妙的方法：

*  先用一个数组c记录子串各个字符出现的次数，再定义一个变量cnt用于统计窗口中有效子串字符数量；
 *  滑动窗口，窗口头每向前移动一个字符，数组c减去一个该字符出现的次数，若该字符出现次数 >= 0，说明该值属于有效子串字符，++cnt；
 *  当cnt 等于子字符串长度，说明次数窗口中包含T所以字符，此时需要滑动窗口，窗口尾向前移动；
 *  滑动窗口，窗口尾每向前移动一个字符，数组c加上一个该字符出现的次数，若该字符出现次数 > 0，说明该值属于有效子串字符，--cnt；

这里通过数组c，和变量cnt能很巧妙的判断当前字符是否属于子串的有效字符。这种方法值得回味、学习。

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 076_MinWindow.h
    * @label   : 字符串滑动窗口
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107570145
    * @author  : niebingyu
    * @date    : 2020/07/24
    * @title   : 76.最小覆盖子串
    * @purpose : 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
    *
    * 示例：
    *   输入: S = "ADOBECODEBANC", T = "ABC"
    *   输出: "BANC"
    *
    * 说明：
    *   如果 S 中不存这样的子串，则返回空字符串 ""。
    *   如果 S 中存在这样的子串，我们保证它是唯一的答案
    *
    * 来源：力扣（LeetCode）
    * 难度：困难
    * 链接：https://leetcode-cn.com/problems/minimum-window-substring/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_MINWINDOW namespace NAME_MINWINDOW {
    #define NAMESPACE_MINWINDOWEND }
    NAMESPACE_MINWINDOW
    class Solution 
    {
    public:
        string minWindow(string s, string t) 
        {
            vector<int> c(128,0);
            for(int i = 0; i < t.size(); i++) ++c[t[i]];
            
            int cnt = 0, left = 0, minLeft = -1, minLen = INT_MAX;
            for(int i = 0; i < s.size(); i++)
            {
                if(--c[s[i]] >= 0) ++cnt;
                while(cnt == t.size())
                {
                    if(minLen > i - left + 1)
                    {
                        minLen = i - left + 1;
                        minLeft = left;
                    }
    
                    if(++c[s[left]] > 0) --cnt;
                    ++left;
                }
            }
    
            return minLeft == -1 ? "" : s.substr(minLeft, minLen);
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, string str, string t, string expect)
    {
        Solution s;
        string result = s.minWindow(str, t);
    
        if (result == expect)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    void Test1()
    {
        string st = "ADOBECODEBANC";
        string t = "ABC";
        string expect = "BANC";
        test("Test1()", st, t, expect);
    }
    
    NAMESPACE_MINWINDOWEND
    // 测试 用例 END
    //
    void MinWindow_Test()
    {
        cout << "------ start 76.最小覆盖子串 ------" << endl;
        NAME_MINWINDOW::Test1();
        cout << "------ end 76.最小覆盖子串 --------" << endl;
    }

**执行结果：**

![20200724213723391.png][]

[https_leetcode-cn.com_problems_minimum-window-substring]: https://leetcode-cn.com/problems/minimum-window-substring/
[20200724213723391.png]: /images/20230208/5e341a734a934a7c9e63d1df33a3da5e.png