leetcode 76. 最小覆盖子串

题目描述

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。

示例:
输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”

说明:
如果 S 中不存这样的子串,则返回空字符串 “”。
如果 S 中存在这样的子串,我们保证它是唯一的答案。

题解

双指针,滑动窗口

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func minWindow(s string, t string) string {
res := ""
left, right := 0, 0
n := len(s)
hashS := make(map[byte]int)
hashT := make(map[byte]int)
for _, v := range t {
hashT[byte(v)]++
}
for right < n {
hashS[s[right]]++
for left <= right && contains(hashS, hashT) {
if res == "" {
res = s[left:right+1]
}
if len(res) > right-left+1 {
res = s[left:right+1]
}
hashS[s[left]]--
left++
}
right++
}
return res
}

func contains(hashS, hashT map[byte]int) bool {
for k, v := range hashT {
if hashS[k] < v {
return false
}
}
return true
}