LeetCode100-76最小覆盖子串

本文基于各个大佬的文章

上点关注下点赞，明天一定更灿烂！

---

前言

        Python基础好像会了又好像没会，所有我直接开始刷leetcode一边抄样例代码一边学习吧。本系列文章用来记录学习中的思考，写给自己看的，也欢迎大家在评论区指导~

        您的每一条评论都会让我更有学习的动力。

---

一、分析题目

这个题可以稍微参考一下LeetCode100-3无重复字符的最长子串（滑动窗口）-CSDN博客

这个题目当时借助了哈希表和窗口函数

二、思路以及代码

思路：利用可变滑动窗口技术，同时用哈希表记录t中字符的频率和窗口中字符的频率

我不会，还是借助一下科技手段把。

from collections import defaultdict
def minWindow(s: str, t: str) -> str:# 边界条件处理if not s or not t or len(s) < len(t):return ""# 构建t的字符频率哈希表target_count = defaultdict(int)for char in t:target_count[char] += 1# 窗口字符频率哈希表window_count = defaultdict(int)# 需要满足的字符种类数required = len(target_count)# 当前满足条件的字符种类数satisfied = 0# 左右指针left = 0# 最小窗口的起始索引和长度min_start, min_length = 0, float('inf')# 右指针遍历sfor right in range(len(s)):char = s[right]window_count[char] += 1# 如果当前字符是目标字符且数量达到要求，增加satisfiedif char in target_count and window_count[char] == target_count[char]:satisfied += 1# 当窗口包含t所有字符时，尝试缩小窗口while satisfied == required and left <= right:# 更新最小窗口current_length = right - left + 1if current_length < min_length:min_length = current_lengthmin_start = left# 移动左指针，缩小窗口left_char = s[left]window_count[left_char] -= 1# 如果左指针字符是目标字符且数量不再满足要求，减少satisfiedif left_char in target_count and window_count[left_char] < target_count[left_char]:satisfied -= 1left += 1# 返回最小窗口或空字符串return s[min_start:min_start + min_length] if min_length != float('inf') else ""

运行成功咯

三、本题收获

defaultdict 是 Python 的 collections 模块中提供的一个字典类。它与普通的字典 (dict) 非常类似，但有一个关键的区别：当访问一个不存在的键时，defaultdict 不会抛出 KeyError 异常，而是会调用一个工厂函数来为该键提供一个默认值。

from collections import defaultdict# 创建 defaultdict，需要传入一个工厂函数作为参数
# 工厂函数负责为不存在的键生成默认值# 示例 1: 默认值是整数 0
d = defaultdict(int)  # int() 的默认值是 0# 示例 2: 默认值是列表 []
d = defaultdict(list)  # list() 的默认值是 []# 示例 3: 默认值是字符串 ""
d = defaultdict(str)  # str() 的默认值是 ""# 示例 4: 使用自定义的工厂函数
def my_default_value():return "default value"d = defaultdict(my_default_value)

---

总结

        只会打暴力，基础一团糟，明天再学吧老铁，别真学会了。