LeetCodes刷题总结4——最小覆盖子串

LeetCodes刷题总结4——最小覆盖子串,第1张

题目

76. 最小覆盖子串 - 力扣(LeetCode) (leetcode-cn.com)

思路

这道题非常经典,属于滑动窗口的经典思想。

首先看到这题估计很多人会去想动态规划,看当前子串与字符串t的关系,但是你会想动态规划方程怎么写?可能几乎没有出路。

好吧,任何算法都是暴力求解优化来的,我们先想暴力算法,把字符串s的所有子串都拿出来去看有没有覆盖字符串t,一定可行但是想都不要想一定超时,那么我们考虑剪枝,这个子串一定大于等于t,不然不可能覆盖(注:题目要求结果覆盖t的所有字符串,包括重复的)。这样我们考虑滑动窗口思想。

顾名思义,滑动窗口在字符串s上定义两个左右边界,不断移动左边界或右边界寻找答案。在此之前我们先考虑一个问题,假设你现在确定好了边界,怎么判断这个子串覆盖了t没?估计你会想对于这个子串一个个遍历,找个变量记录覆盖t的字符数。但是这样做又陷入了高时间复杂度的循环中。我们考虑用map来记录当前子串各字符个数和t的各字符个数,在移动边界之前先把t的map填好,同时保留记录覆盖t的字符数的变量(我设为num)。这样做不管子串怎样变我们只要对子串的map进行增删不就可以了吗?

然后再看移动边界的策略。我们首先初始化左右边界(left=0,right=-1,-1是为了便于循环),然后先移动右边界,在移动的过程中不断增加子串map的内容,同时记录num,当num=t.length()时,说明一个结果出来了,此时先移动左边界剔除左边多余的值,再将结果暂存。然后此时左边界再向右移动,num减一,再去移动右边界重复上面的过程。

当然上面的文字一看就迷乱了,可能不知道我在说什么。这是就拿出纸笔或者电脑画板,找个简单的例子,边画边想边敲代码。我认为这是一个非常好的做法,因为很多细节只有自己慢慢推敲才不容易乱。

 上面是我随手画的图,其实一点也不精致,但是非常便于自己理清思路。

代码

我的代码思路并不新,复杂度也不占优,细节都在注释里面了,仅供参考。

#include
#include
#include

using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        int s_len=s.length();
        int t_len=t.length();
        string res="";
        //判断临界条件
        if(s_len==0||t_len==0||s_len s_map,t_map;
        //先把t各元素个数记录下来
        for(char c:t){
            t_map[c]++;
        }
        int l=0;
        int r=-1; //滑动窗口的左右边界
        string temp; //s的子串暂存
        int num=0; //temp覆盖t的字符个数
        int len=INT_MAX;
        //正常右边界向前
        while(r>s;
    cin>>t;
    string res;
    res=Solution().minWindow(s,t);
    cout<

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/707501.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-24
下一篇 2022-04-24

发表评论

登录后才能评论

评论列表(0条)