python每日一题——12最小覆盖子串
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2:
输入:s = “a”, t = “a”
输出:“a”
解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
答案
这道题可以用滑动窗口来解决。我们可以统计字符串 t 中每个字符的出现次数,并用一个滑动窗口在字符串 s 中移动。窗口的大小与 t 中字符的总数相同。
在每次移动窗口的过程中,我们检查窗口中的字符是否能够覆盖 t 中的所有字符。如果可以,我们就找到了一个解,可以移动窗口并继续搜索;如果不能,我们就需要缩小窗口的大小,然后再继续搜索。
以下是对应的 Python 代码:
from collections import Counter
def min_covering_substring(s, t):
# 使用 collections.Counter 统计字符串 t 中每个字符的出现次数
t_counts = Counter(t)
res = ""
left = 0
# 窗口的大小为 t 中字符的总数
for right in range(len(s) + 1):
# 窗口中字符的计数
s_counts = Counter(s[left:right+1])
# 检查窗口中的字符是否能够覆盖 t 中的所有字符
if all(s_counts[c] >= t_counts[c] for c in t_counts):
# 如果可以,更新答案
res = s[left:right+1]
# 如果不能,缩小窗口的大小
while not all(s_counts[c] >= t_counts[c] for c in t_counts):
s_counts[s[left]] -= 1
left += 1
return res
在这段代码中,首先使用 collections.Counter
统计字符串 t
中每个字符的出现次数,保存在 t_counts
中。然后初始化结果字符串 res
为空字符串,初始化左指针 left
为 0。然后开始一个循环,右指针 right
从 0 开始,每次迭代把 right
向右移动一格,并统计窗口内字符的频次 s_counts
。如果 s_counts
中的每个字符的频次都不小于 t_counts
中对应的字符频次,那么更新 res
。然后进入一个内部循环,如果窗口内字符频次 s_counts
中的每个字符的频次仍然不小于 t_counts
中对应的字符频次,那么就继续将 left
向右移动一格,并从 s_counts
中减去移出的字符频次。最后返回 res
。