算法刷题 —— 最小覆盖子串(Leetcode 76)

2024-03-20 约 310 字预计阅读 1 分钟次阅读

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" ~

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


func main(){
	var res string
	var s , t string

	// 示例 1
	s , t = "ADOBECODEBANC", "ABC"
	res = minWindow(s,t)
	fmt.Println("res:",res)

	// 示例 2
	s , t = "a", "a"
	res = minWindow(s,t)
	fmt.Println("res:",res)

	// 示例 3
	s , t ="a", "aa"
	res = minWindow(s,t)
	fmt.Println("res:",res)
}

// 采用滑动窗口的方法来进行求解
func minWindow(s string, t string) string {
    res := ""
    length := math.MaxInt32
    mp := make(map[byte]int)
    for i := 0 ; i < len(t) ; i++ {
        mp[t[i]]++
    }

    left := 0  // 滑动窗口左边界
    right := 0 // 滑动窗口右边界
    for right < len(s) {
        mp[s[right]]--
        for check(mp) { // 判断当前mp是否有效
            if right - left + 1 < length {
                length = right - left + 1
                res = s[left : right+1]
            }
            mp[s[left]]++
            left++
        }
        right++
    }
    return res
}

func check(mp map[byte]int) bool { // 有效
    for _ , v := range mp {
        if v > 0 {
            return false
        }
    }
    return true
}

目录

算法刷题 —— 最小覆盖子串(Leetcode 76)