[python 刷题] 76 Minimum Window Substring
题目:
这道题我用的解法和 [python 刷题] 567 Permutation in String 一样的,不过 [python 刷题] 567 Permutation in String 要求找到完全一致的配对,而这道题可以允许子字符串包含重复和多余的字符。
以 LC 给的案例来说 Input: s = "ADOBECODEBANC", t = "ABC"
,满足 ABC
只出现了一次的子字符串有三个:
题目中要求的是长度最短的字符串,因此满足要求的就是 BANC
[python 刷题] 567 Permutation in String 是在满足需求,即找到包含 t
的子字符串就返回 True
,这里只需要做一个最简单的修改,就是完成对整个数组的循环,并且在满足 !current_selected_str
或 r - l + 1 < current_selected_str
两个情况下,更新 current_selected_str
即可
代码如下:
class Solution:
def minWindow(self, s: str, t: str) -> str:
tc, sc = collections.Counter(t), collections.Counter()
def has_substring():
for c in tc:
if sc[c] < tc[c]:
return False
return True
l = 0
res = ''
for r, c in enumerate(s):
sc[c] += 1
while sc[s[l]] > tc[s[l]] and l < r:
sc[s[l]] -= 1
l += 1
if has_substring():
if not len(res) or r - l + 1 < len(res):
res = s[l:r + 1]
return res