题目:
最小覆盖子串:给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。
说明:
- 如果 S 中不存这样的子串,则返回空字符串
""
。
- 如果 S 中存在这样的子串,我们保证它是唯一的答案。
思路:
使用滑动窗口法。
程序:
from collections import defaultdict
class Solution:
def minWindow(self, s: 'str', t: 'str') -> 'str':
if not s or not t:
return ""
findOut = defaultdict(int)
for letter in t:
findOut[letter] += 1
index1 = 0
index2 = 0
counter = len(t)
length = len(s)
min_len = float("inf")
result = ""
while index2 < length:
if findOut[s[index2]] >= 1:
counter -= 1
findOut[s[index2]] -= 1
index2 += 1
while counter == 0:
if min_len > index2 - index1:
min_len = index2 - index1
result = s[index1 : index2]
if findOut[s[index1]] == 0:
counter += 1
findOut[s[index1]] += 1
index1 += 1
return result