leetcode 76. 最小覆盖子串

题解

双指针,滑动窗口

示例代码(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
}