LeetCode-76.最小覆盖子串 - sheep44044的小站

滑动窗口#

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

示例 1：

1
输入：s = "ADOBECODEBANC", t = "ABC"
2
输出："BANC"
3
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
输入：s = "a", t = "a"
2
输出："a"
3
解释：整个字符串 s 是最小覆盖子串。

示例 3:

1
输入: s = "a", t = "aa"
2
输出: ""
3
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
4
因此没有符合条件的子字符串，返回空字符串。

1.一个正确的答案

刚开始做被爆了捏，做不出来

不过事后看其实也还好，没想象的可怕

思路：1.判断出s包含了t 2.使用滑动窗口，让它左右互搏，推断出最小值

这里的难点是是如何高效地判断s包含了t？

答：多引入几个变量，need、valid、needcount和window，表示不同的状态量，都匹配了就是包含。

关于这里的滑动窗口，我认为可以参考904. 水果成篮是差不多的

1
func minWindow(s string, t string) string {
2
    left, right := 0, 0
3
    var need, window [128]int
4
    needcount, valid := 0, 0
5
    minlen := 100001
6
    start := 0
7

8
    for _, i := range t {
9
        need[i]++
10
        if need[i] == 1 {
11
            needcount++
12
        }
13
    }
14

15
    for right < len(s) {
16
        c := s[right]
17
        if need[c] > 0 {
18
            window[c]++
19
            if window[c] == need[c] {
20
                valid++
21
            }
22
        }
23

24
        for valid == needcount {
25
            if right - left + 1 < minlen {
26
                start = left
27
                minlen = right - left + 1
28
            }
29

30
            d := s[left]
31
            if need[d] > 0 {
32
                window[d]--
33
                if window[d] < need[d]{
34
                    valid--
35
                }
36
            }
37
            left++
38
        }
39

40
        right++
41
    }
42

43
    if minlen == 100001 {
44
        return ""
45
    }
46

47
    return s[start : start+minlen]
48
}