开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

LeetCode 76. 最小覆盖子串

简介: LeetCode 76. 最小覆盖子串
+关注继续查看

76. 最小覆盖子串


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


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


示例 1:


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


示例 2:


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


题解:滑动窗口


image


本题使用滑动窗口求解,即两个指针 l 和 r 都是从最左端向最右端移动,且 l 的位置一定在r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环,但是因为 while 循环负责移动 l 指针,且 l 只会从左到右移动一次,因此总时间复杂度仍然是 O(n)。本题使用了长度为 128 的数组来映射字符,也可以用哈希表替代;其中 chars 表示目前每个字符缺少的数量,flag 表示每个字符是否在 T 中存在


更多可参考官方题解:https://leetcode-cn.com/problems/minimum-window-substring/solution/tong-su-qie-xiang-xi-de-miao-shu-hua-dong-chuang-k/


代码


class Solution {
public:
    string minWindow(string s, string t) {
        // 一共就128个字符 chars记录每个字符的数量,flag记录是否存在这个字符
        vector<int> chars(128,0);
        vector<bool> flag(128,false);
        // 先统计T中拥有的字符情况
        for(int i=0;i<t.size();i++)
        {
            chars[t[i]]++;
            flag[t[i]]=true;
        }
        int count=0,l=0,min_l=0,min_size=s.size()+1;
        for(int r=0;r<s.size();r++)
        {
            // 如果当前遍历到的字符在t中存在
            if(flag[s[r]])
            {       
                if(--chars[s[r]]>=0)
                {
                    count++; 
                }
                // 如果当前滑动窗口包含了 t 中所有的字符,那么尝试将 l 向左移,在不影响满足条件的情况下获得最短情况
                while(count==t.size())
                {
                    // 如果当前包含了所有的 t中字符,并且长度小于当前最小,那么重新赋值
                    if(r-l+1<min_size)
                    {
                        min_size=r-l+1;
                        min_l=l;
                    }
                    if(flag[s[l]]&&++chars[s[l]]>0)
                    {
                        count--;
                    }
                    l++;    // l 右移动(不需要担心破坏满足条件,因为上面的判断已经保存了最小的)
                }
             }
        }
        return min_size>s.size()?"":s.substr(min_l,min_size);
    }
};

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
「LeetCode」101-对称二叉树⚡️
「LeetCode」101-对称二叉树⚡️
21 0
LeetCode 64. 最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
113 0
LeetCode刷题101-简单-对称二叉树
LeetCode刷题101-简单-对称二叉树
18 0
LeetCode刷题155-简单-最小栈
LeetCode刷题155-简单-最小栈
41 0
LeetCode 训练场:110. 平衡二叉树
LeetCode 训练场:110. 平衡二叉树
25 0
LeetCode 18. 早餐组合
LeetCode 18. 早餐组合
23 0
Leetcode77组合(回溯求解)
Leetcode77组合(回溯求解)
16 0
LeetCode题解—二叉树
今天说说二叉树。
28 0
LeetCode 动态规划之三角形最小路径和
LeetCode 动态规划之三角形最小路径和
20 0
Leetcode120三角形最小路径和
Leetcode120三角形最小路径和
13 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载