1. 首页

076. 最小覆盖子串

题目描述:

难度:Hard

相关话题:哈希表双指针字符串Sliding Window

给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。

示例:

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

说明:

  • 如果 S 中不存这样的子串,则返回空字符串 ""

  • 如果 S 中存在这样的子串,我们保证它是唯一的答案。


思路:

首先对t的字母建立count,以出现频率作为它的值,由于题目没有明确说明大小写,因此设定128位。

变量tLen表示t的长度;

变量preID表示当前一个滑动区间的最左侧的索引;

变量startend表示最小区间的左索引和右索引。

遍历s

如果count[s.charCodeAt(i)]-->0,说明s[i]属于t,需要tLen--

如果tLen===0,说明t中的值已经全部在区间[preID,i]出现了,比较区间[preID,i][start,end],如果更小,更新[start,end]

检查count[s.charCodeAt(preID++)]++==0,如果条件成立,说明preID索引刚好调整到跳过1个存在t中的字母,并且这个字母当前已经不存在与[preID,i]区间内。

遍历完毕后,返回区间[start,end],如果不存在,则返回''

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
  let count=Array(128).fill(0)
  let tLen=t.length
  for(let w of t){
    let code=w.charCodeAt(0)
    count
++ } // console.log(count) let preID=0,start=0,end=Infinity,curLen=0 for(let i=0;i<s.length;i++){ if(count[s.charCodeAt(i)]-->0){ tLen-- } while(tLen===0){ if(i-preID<end-start){ end=i+1 start=preID } if(count[s.charCodeAt(preID++)]++==0) tLen++ } } return end===Infinity?'':s.substring(start,end) };

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:076. 最小覆盖子串

链接:https://www.javascriptc.com/4436.html

« Git操作文件的时候手贱了,怎么恢复?
075. 颜色分类»
Flutter 中文教程资源

相关推荐

QR code