1. 题目描述
给你一个字符串 S、一个字符串 T 。请你设计一种算法,可以在 O(n) 的时间复杂度内,从字符串 S 里面找出:包含 T 所有字符的最小子串。
示例:
输入:S = "ADOBECODEBANC", T = "ABC"
输出:"BANC"
提示:
- 如果 S 中不存这样的子串,则返回空字符串 “”。
-
2. 解题思路
这题目可以使用双指针+map实现。
首先,定义一个map,将子串所需要的字符及其个数存贮在map中
- 定义两个指针,来维护一个滑动窗口
- 右指针往后移动,如果发现当前的右指针的值在map中存在,就map中该元素需要的个数减一,如果该元素需要的个数为0,那总需要的个数needType也减一
- 如果需要的元素个数为0(也就是左右指针之间已经包含了所需字符),那么就向右移动左指针来缩小范围,同时如果map中需要该元素,就往其中加一,需求数也加一。
- 在缩小范围的同时,截取两指针之间的字符串,找出最短的字符串即可
该算法的时间复杂度为O(m+n),m和n分别是两个字符串的长度,所以符合题目要求的O(n)的时间复杂度。空间复杂度是O(m),m是s字符串的长度。
3. 代码实现
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
let l = 0
let r = 0
const need = new Map() // 表示子串的字符及个数
for(let i of t){
need.set(i, need.has(i) ? need.get(i)+1 : 1 )
}
let needtype= need.size
let res = ''
// 移动右指针
while(r< s.length){
const c= s[r]
// 如果右指针当前的值在子串中存在,则need中该字符数也-1
if(need.has(c)){
need.set(c, need.get(c) - 1)
if(need.get(c) === 0) needtype -= 1 //如果这个字符需要数为0,则需要的个数为-1
}
// 子串已包含所有需要的字符,用该循环来缩小字串的长度
while(needtype === 0){
// 截取子串,找出最小长度的子串
const newRes = s.substring(l, r+1)
if(!res || newRes.length < res.length) res = newRes
const c2 = s[l]
// 移动左指针,如果左指针在需要的子串里面,需求数就+1
if(need.has(c2)){
need.set(c2, need.get(c2)+ 1 )
if(need.get(c2) === 1) needtype += 1
}
l += 1
}
r += 1
}
return res
};