题目描述:
难度:Hard
相关话题:哈希表
、双指针
、字符串
、Sliding Window
给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明:
- 如果 S 中不存这样的子串,则返回空字符串
""
。 -
如果 S 中存在这样的子串,我们保证它是唯一的答案。
思路:
首先对t
的字母建立count
,以出现频率作为它的值,由于题目没有明确说明大小写,因此设定128
位。
变量tLen
表示t
的长度;
变量preID
表示当前一个滑动区间的最左侧的索引;
变量start
和end
表示最小区间的左索引和右索引。
遍历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)
};
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程