最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • JS算法-最小覆盖子串

    正文概述 掘金(一个前端王)   2021-05-04   61

    本题来自leetcode 第 76 题

    题目描述

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

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

    示例 1:

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

    示例 2:

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

    提示:

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

    解题思路

    • 首先遍历子串t,并且设置map值。例如:子串t = "ABC",Map(3) {"A" => 1, "B" => 1, "C" => 1}。记录map的size值。

    • 然后右指针开始向后走,每找到一个map中存在的字符,该字符对应的值减1,该字符的值减为0时,map的size减1。

    • 直到map的size为0时,开始移动左指针,并且记录当前的子串。

    • 左指针移动过程中,每找到一个字符,设置map,size加1,接着继续外层循环,移动右指针。下次map的size减为0时,再移动左指针。

    • 每次开始移动左指针时,当前子串是符合题目要求的情况,比较子串长度并取最小的子串即可取到最短符合条件的子串。

    代码展示

    双指针 + 哈希表 + 滑动窗口 + 字符串

    /**
     * @param {string} s
     * @param {string} t
     * @return {string}
     */
    var minWindow = function(s, t) {
        const len = s.length;
        const map = new Map();
        let l = 0, r = 0, res = '';
        for (let i = 0; i < t.length; i++) {
            const c = t[i];
            map.set(c, map.get(c) ? map.get(c) + 1 : 1);
        }
        let mapSize = map.size;
        while (r < len) {
            const c1 = s[r];
            if (map.has(c1)) {
                map.set(c1, map.get(c1) - 1)
                if (map.get(c1) === 0) mapSize -= 1;
            }
            while(mapSize === 0) {
                const newRes = s.substring(l, r + 1);
                if (!res || res > newRes) {
                    res = newRes;
                }
                const c2 = s[l];
                if (map.has(c2)) {
                    map.set(c2, map.get(c2) + 1);
                    if (map.get(c2) === 1) mapSize += 1;
                }
                l += 1;
            }
            r += 1;
        }
        return res;
    }
    

    复杂度分析:

    时间复杂度:O(m + n)。m是字符串s的长度,n是字符串t的长度。

    空间复杂度:O(k)。k是t中不重复字符的长度。

    总结

    这道题对于理解双指针,滑动窗口,以及map数据类型和字符串操作挺有帮助。


    起源地 » JS算法-最小覆盖子串

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元