# 76. 最小覆盖子串
难度：困难
# 题目：
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 105s和t由英文字母组成
** 进阶：** 你能设计一个在 o(n) 时间内解决此问题的算法吗？
# 想法：
# 1. 暴力 (超时)
当看到这道题时，我第一想法是动态规划，构建一个 大小的辅助数组，用 表示 s 中第 个到第 个字符包含所需字符的个数，当 的时候跳出当前循环，记录下来 和之前结果的长度，比原先的小，就更新结果。最坏情况下是。不出意料，结果超时了
class Solution(object): | |
def minWindow(self, s, t): | |
""" | |
:type s: str | |
:type t: str | |
:rtype: str | |
""" | |
length = len(s) | |
#辅助数组 | |
help = [[0] * length for i in range(length)] | |
min = 10000 | |
res = "" | |
for i in range(length-len(t)+1): | |
tmp =t | |
for j in range(i,length): | |
if s[j] in tmp: | |
tmp=tmp.replace(s[j],'',1) | |
if j>=i: | |
help[i][j]=help[i][j-1]+1 | |
if help[i][j]==len(t): | |
if j - i < min: | |
min = j - i | |
res = s[i:j + 1] | |
break | |
else: | |
help[i][j] =1 | |
else: | |
if j > i: | |
help[i][j] = help[i][j-1] | |
return res |
# 双指针
第二想法是双指针滑动窗口，具体做法是定义两个指针,。和一个待匹配字符串中字母所需个数的字典 need, 和还需要的字符个数。当 时， 右移，同时根据当前字符更新 和，直到包含全部所需字符 时， 右移，并更新 和。直到 到达 且 到达 为止。
class Solution(object): | |
def minWindow(self, s, t): | |
""" | |
:type s: str | |
:type t: str | |
:rtype: str | |
""" | |
#将待匹配字符串中字母所需个数存入字典中 | |
need ={} | |
for i in t: | |
if i in need.keys(): | |
need[i]=need[i]+1 | |
else: | |
need[i]=1 | |
#记录所需字符的最大个数，(这个字典保持不动，只记录最大值) | |
help=need.copy() | |
#head tail count needCount | |
head=0 | |
tail=0 | |
needCount=len(t) | |
res="" | |
minLength=float('inf') | |
while head<len(s) or tail<len(s)-len(t)+1: | |
#判断当前字符是 head 指向的还是 tail 指向的 | |
currentChar=s[head] if 0 < needCount and head<len(s) else s[tail] | |
#未包含所需的所有字符 | |
if 0 < needCount: | |
#当首指针未到尾部 | |
if head < len(s): | |
#当前字符是所需要的 | |
if currentChar in t: | |
#需要的数目 - 1 / 不变 | |
needCount=needCount-1 if need[currentChar]>0 else needCount | |
#所需字符 - 1 | |
need[currentChar]=need[currentChar]-1 | |
#当匹配时更新结果 | |
if needCount==0: | |
if head-tail+1<minLength: | |
res=s[tail:head+1] | |
minLength=head-tail+1 | |
head=head+1 | |
else: | |
#当首指针到达尾部，且 needCount>0 | |
return res | |
#当已经包含所需的全部字符时 | |
else: | |
# 当前字符是所需要的 | |
if currentChar in t: | |
# 需要的数目 + 1 / 不变 | |
needCount = needCount + 1 if need[currentChar] ==0 else needCount | |
## 所需字符 + 1 (不能超过原有值) | |
need[currentChar]=need[currentChar]+1 if need[currentChar]<help[currentChar] else need[currentChar] | |
tail=tail+1 | |
# 当匹配时更新结果 | |
if needCount == 0: | |
#当 head 未到尾部时 | |
if head<len(t): | |
if head - tail + 1 < minLength: | |
res = s[tail:head + 1] | |
minLength = head - tail + 1 | |
else: | |
#当 head 到尾部后，head=len (s) 所以无需 + 1 了 | |
if head - tail< minLength: | |
res = s[tail:head] | |
minLength = head - tail | |
return res |
