题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
- 注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
- 示例
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
思路
滑动窗口算法/快慢指针算法，我这是卡在细节许久了，找到了如下的解决办法，也学到了一点新的知识点。具体可以参考https://emperinter.com/2022/01/26/20220126/
- 本地调试的完整代码
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
#Base Condition
if not s or not t: return ""
t_counter = Counter(t)
left = right = 0
# 滑动窗口里面的数据
window_dict = {}
result = []
while right < len(s):
# 把当前的字符加到滑动窗口里面并且判断是否满足条件
# dict的默认方法：
# dict.get(key, default=None)
# 返回指定键的值，如果键不在字典中返回默认值 None 或者指定的默认值。
window_dict[s[right]] = window_dict.get(s[right], 0) + 1
if self.isFit(window_dict, t_counter):
# 如果满足条件就开始移动left指针
while left <= right:
print("right:" + str(right) + "\tleft:" + str(left))
# 把当前的字符从滑动窗口里面移出
window_dict[s[left]] -= 1
left += 1
# 因为话单窗口是左闭右开，所以是not，并以此为判断。
if not self.isFit(window_dict, t_counter):
# 结果列表是一个sd的字符串
result.append(s[left - 1:right + 1])
break
right += 1
print(result)
return sorted(result, key=lambda i: len(i))[0] if result else ""
# 判断滑动窗口里面的数据是否满足t的需求量
def isFit(self, window_dict: dict, t_counter: Counter) -> bool:
for each_t in t_counter:
if t_counter[each_t] > window_dict.get(each_t, 0):
return False
return True
S = Solution()
minStr = S.minWindow("ADOBECODEBANCABCC","ABCCD")
print("#########################")
print(minStr)
