76. Minimum Window Substring
给你两个 string s and t 问你能让 t 的每个字符都出现的 s 的最短 substring
t 会包含 duplicate characters
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Example 2:
Input: s = "a", t = "a"
Output: "a"
Example 3:
Input: s = "a", t = "aa"
Output: ""
思路:
1.因为 substring 是连续的可以用左界右界去检查 如果 t 不会重复就简单了
维护一个 set 和 set(t), left right 都从 0 开始
如果目前子字串合法就推进 left 反之推进 right
推进 left 的意思: 拔掉 s[left], 检查 s[left] 有没有在 set(t) 里 有就拔掉
推进 right 的意思: 加进 s[right], 检查 s[right] 有没有在 set(t) 里 有就加
合不合法就是看目前 set 的长度有没有跟 set(t) 的长度一样
2.但是 t 会重复 所以改用 dict 概念还是差不多就是
这里要再开一个 dict 去和 dict(t) 比较也是可以 只是 code 会变得很长
所以稍微改变一下 dict 的意思 不是字符目前出现的数量 而是还缺多少个
这样就能算完 t 的数量之后把 tdict = Counter(t) 直接拿来用
另外检查合不合法也多开一个变量去记 意思也是目前差多少个目标字符 tlen = len(t)
推进 left: tdict[s[left]] += 1 意思是拔掉 s[left] 后他的需求数量变多了
tlen += (tdict[s[left]] > 0) 如果拔掉会让他的需求超过 1 就加上去
这里要多检查是因为有些 s 的字符一开始不会出现在 tdict 中
所以要想办法在更新 tlen 的时候忽略掉他们 而因为字符一定是先被 right 碰到
也就是先加入后移除 所以一开始不在 tdict 当中的字符 他的需求数量一定是 <= 0
这种字符我们在更新 tlen 时就不用理他了 不会影响合不合法
最后 怎么检查合不合法? 就是看 tlen 等不等于 0
Python code:
class Solution:
def minWindow(self, s: str, t: str) -> str:
n, tdict, tlen = len(s), Counter(t), len(t)
left, right = 0, 0
res, reslen = "", float('inf')
while r <= n:
if tlen == 0:
if r-l+1 < reslen:
res = s[l:r]
reslen = r-l+1
tdict[s[l]] += 1
tlen += (tdict[s[l]] > 0)
l += 1
else:
if r == n:
break
tdict[s[r]] -= 1
tlen -= (tdict[s[r]] >= 0)
r += 1
return res
单循环版本 写完觉得跟班长一样丑
再参考一下别人的 iterate 右界 推进左界直到不合法
class Solution:
def minWindow(self, s: str, t: str) -> str:
n, tdict, tlen = len(s), Counter(t), len(t)
left, right = 0, 0
res, reslen = "", float('inf')
for right in range(n):
tlen -= tdict[s[right]] > 0
tdict[s[right]] -= 1
while tlen == 0:
if right-left < reslen:
res = s[left:right+1]
reslen = right-left
tdict[s[left]] += 1
tlen += tdict[s[left]] > 0
left += 1
return res
有稍微顺眼一点了

288