给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。- 核心目标: 在字符串 S 中找到最短的子串, 使其包含字符串 T 的所有字符 (包括重复次数).
- 滑动窗口法: 用两个指针维护一个窗口; 右指针扩展窗口直到包含所有目标字符; 左指针收缩窗口以尽量缩短长度; 在过程中不断更新最优解.
- 复杂度分析: 每个字符最多被左右指针访问一次; 时间复杂度 O(n); 空间复杂度 O(m), 其中 m 为 T 的字符种类数.
Python
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import Counter
ret = ''
need = Counter(t) # 需要满足的每种字符数
book = Counter() # 记录出现过的字符数
# def check(): # 检验是否满足情况
# return all(book[k] >= need[k] for k in need)
l, r = 0, 0
while r < len(s):
book[s[r]] += 1
# while check():
while book >= need: # Counter 可以直接比较大小
if not ret or r - l < len(ret): # 更新答案
ret = s[l: r + 1]
book[s[l]] -= 1
l += 1 # 移动左边界
r += 1 # 移动右边界
return ret其他算法笔记
LeetCode Hot 100 (32)
[中等, LeetCode] 三数之和 🔥
[中等, LeetCode] 下一个排列 🔥
[中等, LeetCode] 两数相加 🔥
[中等, LeetCode] 全排列 🔥
[中等, LeetCode] 全排列II 🔥
[中等, LeetCode] 删除链表的倒数第N个结点 🔥
[中等, LeetCode] 和为K的子数组 🔥
[中等, LeetCode] 在排序数组中查找元素的第一个和最后一个位置 🔥
[中等, LeetCode] 字母异位词分组 🔥
[中等, LeetCode] 找到字符串中所有字母异位词 🔥
[中等, LeetCode] 括号生成 🔥
[中等, LeetCode] 搜索旋转排序数组 🔥
[中等, LeetCode] 数组中的第K个最大元素 🔥
[中等, LeetCode] 无重复字符的最长子串 🔥
[中等, LeetCode] 最长回文子串 🔥
[中等, LeetCode] 最长连续序列 🔥
[中等, LeetCode] 电话号码的字母组合 🔥
[中等, LeetCode] 盛最多水的容器 🔥
[中等, LeetCode] 组合总和 II 🔥
[中等, LeetCode] 组合总和 🔥[困难, LeetCode] K个一组翻转链表 🔥
[困难, LeetCode] 合并K个升序链表 🔥
[困难, LeetCode] 寻找两个正序数组的中位数 🔥
[困难, LeetCode] 接雨水 🔥
[困难, LeetCode] 最长有效括号 🔥
[困难, LeetCode] 正则表达式匹配 🔥
[困难, LeetCode] 滑动窗口最大值 🔥
[困难, 牛客] 最小覆盖子串 🔥[简单, LeetCode] 两数之和 🔥
[简单, LeetCode] 合并两个有序链表 🔥
[简单, LeetCode] 有效的括号 🔥
[简单, LeetCode] 移动零 🔥