Keshawn_lu's Blog

Leetcode 76. 最小覆盖子串

哈希表 滑动窗口
字数统计: 599阅读时长: 2 min
2020/05/23 Share

题目简介：

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

示例：

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

说明：

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

思路：

先将T中的字符存入至哈希表中，然后利用滑动窗口的思想，右端窗口不断往右遍历(即扩大窗口)，并将字符压入window中，若发现当前字符出现在T中，并且出现次数也相等时(即str_t[s[right]] == window[s[right]])，将valid++，说明已经有一个字符已经满足要求了。当valid == str_t.size()时，说明所有字符均已满足要求，开始尝试缩小窗口。

当所有字符每次满足要求时(valid == str_t.size())，保存满足要求子串的最小长度及当前的left(即窗口的开始位置)。然后将left不断往右移，将字符逐渐移出(即缩小窗口)。若遇到之前满足要求的字符，由于将当前字符移出后，一定不会再满足要求了，所以valid--，left结束移动的标志时valid != str_t.size()。

当right移动至字符串S的结尾时，结束遍历。

tips:

  • 判断字符是否出现在T的哈希表中时，需要使用find()或其他可行的方法，不能使用str_t[s[right]] > 0的判定方法，这样会时str_t.size()扩大。
  • 结束遍历后，若len为初始值，则不存在这样的子串，返回空，但len的值需要设的大一点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    string minWindow(string s, string t) {
        
        unordered_map <char, int> window, str_t;
        int left = 0;
        int right = 0;

        int valid = 0;	//满足需求的字符的个数

        for(int i = 0; i < t.length(); i++){

            str_t[t[i]]++;
        }

        int start = 0;
        int len = 1000000;
        while(right < s.length()){    //扩大窗口

            window[s[right]]++; //字符压入窗口
            if(str_t.find(s[right]) != str_t.end()){	//此字符出现在T中

                if(window[s[right]] == str_t[s[right]])	//出现次数相等
                    valid++;
            }
            right++;

            while(valid == str_t.size()){

                if(right - left < len){

                    start = left;
                    len = right - left;
                }

                
                if(str_t.find(s[left]) != str_t.end()){     //缩小窗口

                    if(window[s[left]] == str_t[s[left]])
                        valid--;
                }
                window[s[left]]--;
                left++;
            }
        }

        return len == 1000000 ? "" : s.substr(start, len);

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网