DFS Algorithms
最小覆盖子串
给你一个字符串 s ，一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
ls = len(s)
lt = len(t)
start = 0
end = 0
minl = float('inf')
res1 = 0
res2 = 0
dic = {}
for c in t:
dic[c] = dic.get(c, 0) + 1
window = {}
for c in t:
window[c] = 0
valid = 0
# 一般而言，[left, right)/[start, end)的窗口比较大众，因为默认end得往后走一位，打印的时候确实不包括end
while end < ls:
tmp = s[end]
# 更新窗口向右移动之后的window情况
if tmp in window:
window[tmp] += 1
# 如果t中对应的某个元素有两个，那么只有当其满足两个的时候才会+1
# 但是实际上，应该是找到一个就+1捏，但是这样又会导致tmp一直等于某一个数使得valid疯狂自增
# 因此必须是小于等于的时候就可以增加valid了
if window[tmp] <= dic[tmp]:
valid += 1
# end什么时候+1也有说法
end += 1
# debug专用，找到移动规律
# print(start, end)
# 当窗口需要收缩，左边需要减小
while valid == lt:
# 在这里更新最小的覆盖字串
if end - start < minl:
res1 = start
# 说实话长度这里必须必须注意end的意义，左闭右开
res2 = end - start
minl = res2
# 先提取出将要被剔除出窗口的元素，start什么时候+1都行，但得先取值
d = s[start]
start += 1
if window.get(d):
if window[d] == dic[d]:
valid -= 1
window[d] -= 1
if res2:
return s[res1:res1+res2]
else:
return ''找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
ls = len(s)
start = 0
end = 0
valid = 0
res = []
dic = {}
for c in p:
dic[c] = dic.get(c, 0) + 1
window = {}
# window有个优化，就是到后面判定某字符在dic内，然后更新window，就不用重新遍历一次了
for c in p:
window[c] = 0
while end < ls:
tmp = s[end]
# 更新窗口向右移动之后的window情况
if tmp in window:
window[tmp] += 1
if window[tmp] <= dic[tmp]:
valid += 1
end += 1
# debug专用，找到移动规律
# print(start, end)
# 当窗口需要收缩
while valid == len(p):
# 更新异位词的判断
if end - start == len(p):
res.append(start)
d = s[start]
start += 1
if window.get(d):
if window[d] == dic[d]:
valid -= 1
window[d] -= 1
return res无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
ls = len(s)
start = 0
end = 0
maxl = 0
window = {}
jihe = set()
while end < ls:
tmp = s[end]
window[tmp] = window.get(tmp, 0) + 1
end += 1
# debug专用，找到移动规律
# print(start, end)
# 当窗口需要收缩
while window[tmp] > 1:
# 更新异位词的判断
d = s[start]
start += 1
window[d] -= 1
if end - start > maxl:
maxl = end - start
return maxl
