76.最小分类子串
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。测试用例保证答案唯一。
示例 1：
1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:
1
2
3
4
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
题解思路：滑动窗口同向双指针
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
# while版本
初始化 left = 0，right=0
初始化窗口状态 window
初始化答案 ans
while (right < s.size())
# 扩大窗口, 跟新窗口状态
将 nums[right] / s[right] 加入窗口
while (窗口满足条件)
#更新答案
...
# 缩小窗口
将 nums[left] / s[left] 移出窗口
left+=1
right+=1
return ans
# for版本
ans = 初始值
for left in range(n):
window = 初始化窗口状态
for right in range(left, n):
# 扩大右边界
window.add(nums[right])
# 判断当前区间 [left, right]
if 当前区间满足条件:
ans = 更新答案
return ans
Python
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
55
56
# 双指针，滑动窗口，while版本
from collections import Counter, defaultdict
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t)
window = defaultdict(int)
valid = 0
left = 0
right = 0
min_len = float('inf')
ans = ""
while left<=right and right <len(s):
if s[right] in need:
window[s[right]]+=1
if window[s[right]] == need[s[right]]:
valid+=1
while valid == len(need):
if right-left+1<min_len:
min_len=right-left+1
ans = s[left:right+1]
if s[left] in need:
if window[s[left]] == need[s[left]]:
valid -=1
window[s[left]]-=1
left+=1
right+=1
return ans
# 双指针，滑动窗口，for版本
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t)
ans = ""
min_len = float('inf')
for left in range(len(s)):
window = Counter()
for right in range(left, len(s)):
window[s[right]] += 1
ok = True
for c in need:
if window[c] < need[c]:
ok = False
break
if ok:
if right - left + 1 < min_len:
min_len = right - left + 1
ans = s[left:right + 1]
break
return ans