3-7 76.最小覆盖子串
Date:2022-03-13 16:15:53
标签:
- 滑动窗口
题目:76.最小覆盖子串 ( 困难😟 )
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
- 对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。 - 如果
s
中存在这样的子串,我们保证它是唯一的答案。
示例
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
示例 2:
输入:s = "a", t = "a"
输出:"a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
分析
暴力法
滑动窗口
两个指针,l 和 r 组成一个窗口,r 向右移动直到覆盖所有 t,此时向右移动 l,直到最小串都覆盖 t
题解
function minWindow(s: string, t: string): string {
const ori = new Map<string, number>()
const cnt = new Map<string, number>()
const tLen = t.length
const sLen = s.length
for (let i = 0; i < tLen; ++i) {
const val = t.charAt(i)
ori.set(val, ori.get(val) ? ori.get(val) + 1 : 1)
}
let l = 0,
r = -1
let len = Infinity,
ansL = -1,
ansR = -1
while (r < sLen) {
++r
const val = s.charAt(r)
if (r < sLen && ori.has(val)) {
cnt.set(val, cnt.get(val) ? cnt.get(val) + 1 : 1)
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1
ansL = l
ansR = l + len
}
const val = s.charAt(l)
if (ori.has(val)) {
cnt.set(val, cnt.get(val) ? cnt.get(val) - 1 : -1)
}
++l
}
}
return len == Infinity ? '' : s.slice(ansL, ansR)
function check() {
let res = true
ori.forEach((val, key) => {
const cntVal = cnt.get(key) || 0
if (cntVal < val) {
return (res = false)
}
})
return res
}
}
使用
function main() {
const s = 'ADOBECODEBANC'
const t = 'ABC'
console.log('[]:', minWindow(s, t))
}
main()