LeetCode_Day19 | GeekOcean

算法

发布日期: 2021-03-24

更新日期: 2021-03-24

文章字数: 141

阅读时长: 1 分

阅读次数:

[76] 最小覆盖子串

https://leetcode-cn.com/problems/minimum-window-substring/description/

algorithms
Hard (40.57%)
Likes: 1042
Dislikes: -
Total Accepted: 120.1K
Total Submissions: 293.1K
Testcase Example: ‘“ADOBECODEBANC”\n”ABC”‘

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

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

示例 1：

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

示例 2：

输入：s = "a", t = "a"
输出："a"

提示：

1 <= s.length, t.length <= 10⁵
s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

方法1: 双指针(滑动窗口)

思路:

通过设置左右两个指针(left<=right), 在两指针之间形成一个窗口, 每次仅仅移动一侧的指针.
当前窗口未包含t中所需的所有字符串, 则右侧指针右移, 左侧指针不动, 直至满足条件;
此时右侧指针保持不动, 左侧指针移动来获得能满足条件的最小滑动窗口

知道原理后, 需要解决的问题如下:

如何判断滑动窗口中是否包含t中全部字符
1. 设置 flag 数组用来记录t中出现的字母
2. 设置 chars 数组用来记录t中字母出现的次数, 也可当作滑动窗口中还需要相应字母的个数. (当个数为负值则代表该字母有多余)
3. 设置 count 变量来表示滑动窗口已包含t中字母的个数, 当 count == t.size() 时表示当前窗口已包含t中所有字母, 这也是滑动窗口左侧下标右移的条件
4. flag , chars 也可用 hashtable
5. 因为字母 z 对应的ASCII码是 123 , 所以将数组长度设为123即可, 不过将其设置为2的整数幂128更好
如何设置滑动窗口的移动
1. 具体设置见代码注释
2. 注意: 这里设置的滑动窗口的区间为 [left, right) , 左闭右开, 所以区间长度为 right - left + 1

class Solution {
public:
    string minWindow(string s, string t) {
            // chars 存储t中对应字母出现的次数
            // flag 记录t中出现的字母
            vector<int> chars(128, 0);
            vector<bool> flag(128, false);
            for(int i=0; i<t.size(); ++i){
                flag[t[i]] = true;
                ++chars[t[i]];
            }
            int count=0, left=0, min_left = 0, min_size = s.size() + 1;
            // count 代表滑动窗口中已包含t中字符的个数
            // min_left用于记录最小滑动窗口的左侧下标
            // min_size 用于记录最小滑动窗口大小
            for(int right=0; right<s.size(); ++right ){
                if(flag[s[right]]){
                    if(--chars[s[right]]>=0){
                        ++count;
                    }
                    while(count==t.size()){
                        // 更新最小滑动窗口
                        if(right - left + 1 < min_size){
                            min_left = left;
                            min_size = right -left + 1;
                        }
                        // 若左边待滑动元素是t中元素,并且若滑动, 当前滑动窗口不再包含t中所有字符
                        // 待滑动
                        if(flag[s[left]] && ++chars[s[left]] > 0){
                            --count;
                        }
                        // 执行滑动 
                        //左侧向右滑动
                        ++left;
                    }
                }
            }
            return min_size > s.size() ? "" : s.substr(min_left, min_size);
    }
};