题目描述
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
- 对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。 - 如果
s
中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入: s = “ADOBECODEBANC”, t = “ABC”
输出: “BANC”
解释: 最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2:
输入: s = “a”, t = “a”
输出: “a”
解释: 整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
提示:
m == s.length
n == t.length
1 <= m, n <= 105
s
和t
由英文字母组成
代码及解释
func minWindow(s string, t string) string {
// 初始化 sHash 和 tHash,分别用于记录 s 和 t 中的字符及其出现的次数
sHash, tHash := map[byte]int{}, map[byte]int{}
for i := 0; i < len(t); i++ {
tHash[t[i]]++
}
// check 函数用于检查当前的窗口是否包含了 t 中的所有字符
check := func() bool {
for k, v := range tHash {
if sHash[k] < v {
return false
}
}
return true
}
// 初始化最小子串的长度和起始位置
length := len(s) + 1
start := 0
// l 和 r 分别为滑动窗口的左右指针
for l, r := 0, 0; r < len(s); r++ {
if tHash[s[r]] > 0 {
sHash[s[r]]++
}
// 如果当前窗口包含了 t 中的所有字符,则缩小窗口
for check() && l <= r {
// 更新最小子串的长度和起始位置
if length > r-l+1 {
length = r - l + 1
start = l
}
// 移动左指针,并更新 sHash
if _, ok := sHash[s[l]]; ok {
sHash[s[l]]--
}
l++
}
}
// 如果最小子串的长度仍然是初始值,则返回空字符串
if length == len(s)+1 {
return ""
} else {
return s[start : start+length]
}
}
代码解释
初始化哈希表:
sHash, tHash := map[byte]int{}, map[byte]int{} for i := 0; i < len(t); i++ { tHash[t[i]]++ }
创建两个哈希表
sHash
和tHash
来分别存储字符串s
和t
中的字符及其出现的次数。check 函数:
check := func() bool { for k, v := range tHash { if sHash[k] < v { return false } } return true }
check
函数用于检查当前的窗口是否包含了t
中的所有字符。初始化最小子串的长度和起始位置:
length := len(s) + 1 start := 0
length
用于存储最小子串的长度,start
用于存储最小子串的起始位置。滑动窗口移动:
for l, r := 0, 0; r < len(s); r++ { if tHash[s[r]] > 0 { sHash[s[r]]++ } for check() && l <= r { if length > r-l+1 { length = r - l + 1 start = l } if _, ok := sHash[s[l]]; ok { sHash[s[l]]-- } l++ } }
移动右指针
r
并更新sHash
。当窗口包含了t
中的所有字符时,移动左指针l
并缩小窗口。返回结果:
if length == len(s) + 1 { return "" } else { return s[start: start + length] }
返回最小覆盖子串。
这个算法的时间复杂度是O(|S| + |T|),其中 |S| 和 |T| 分别是字符串 s
和 t
的长度。