当前位置：首页 > news >正文

Leetcode刷题记录23——最小覆盖子串

news 2025/5/1 20:44:00

题源：https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked

题目描述：
在这里插入图片描述
思路一：
1. 初始化与预处理

t_count: 统计字符串 t 中每个字符的出现次数。
window_count: 动态记录滑动窗口中 t 相关字符的出现次数。
min_len: 初始设为 float(‘inf’)，确保最终未找到合法窗口时可返回空字符串。
min_start: 记录最小窗口的起始位置。

2. 滑动窗口算法流程

右指针 (right) 扩展:
- 遍历 s，逐个字符加入窗口。
- 更新 window_count 并检查窗口是否满足 t 的字符频率需求（通过 t_is_sub_of_window 方法）。
左指针 (left) 收缩:
- 当窗口满足条件时，尝试不断向右移动左指针以缩小窗口，寻找更优解。
- 每次收缩前更新最小窗口信息（min_len, min_start）。
- 如果收缩后窗口不再满足条件，则停止收缩。

3. 辅助方法 t_is_sub_of_window

目的：判断当前窗口是否包含 t 的所有字符及其所需频率。
实现：
- 遍历 t_count 中的每个字符 k。
- 若 t_count[k] > window_count.get(k, 0)，表示窗口中与 t 对应的的字母数量不足，返回 False。
- 否则，返回 True。

代码实现如下：

class Solution(object):def minWindow(self, s, t):""":type s: str:type t: str:rtype: str"""t_count = {} # 存储t中字符出现的次数window_count = {} # 存储当前窗口中字符出现的次数left = right = 0min_len = float('inf') # 初始化为无穷大min_start = 0# 构造t_countfor i in range(len(t)):if t[i] not in t_count:t_count[t[i]] = 1else:t_count[t[i]] += 1# 寻找最小覆盖字串for right in range(len(s)):char = s[right]if char not in window_count:window_count[char] = 1else:window_count[char] += 1# 当窗口满足条件时，尝试收缩左边界while self.t_is_sub_of_window(t_count, window_count):current_len = right - left + 1if current_len < min_len:min_len = current_lenmin_start = left# 移动左指针并更新窗口left_char = s[left]window_count[left_char] -= 1left += 1return s[min_start:min_start+min_len] if min_len != float('inf') else ""def t_is_sub_of_window(self, t_count, window_count):for k in t_count:if t_count[k] > window_count.get(k, 0):return Falsereturn True