LeetCode刷题实战76:最小覆盖子串
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 最小覆盖子串,我们先来看题面:
https://leetcode-cn.com/problems/minimum-window-substring/
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
题意
输入:S = "ADOBECODEBANC", T = "ABC"
输出:"BANC"
提示:
如果 S 中不存这样的子串,则返回空字符串 ""。
如果 S 中存在这样的子串,我们保证它是唯一的答案。
解题
分析
解题的套路
题解
# 存储区间内的字符
segement = {}
for i in range(n):
segement[s[i]] += 1
# 当满足条件的时候移动区间左侧
while l <= i and satisified(segment):
# 更新最佳答案
if i - l + 1 < ans_len:
ans_len = i - l + 1
beg, end = l, i + 1
# 弹出元素
segement[s[l]] -= 1
l += 1
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import Counter, defaultdict
# 通过Counter直接获取T当中的字符构成
counter = Counter(t)
n, m = len(s), len(counter)
l, beg, end = 0, 0, 0
cur = defaultdict(int)
matched = 0
flag = False
# 记录合法的字符串的长度
ans_len = 0x3f3f3f3f
for i in range(n):
if s[i] not in counter:
continue
cur[s[i]] += 1
# 当数量匹配上的时候,matched+1
if cur[s[i]] == counter[s[i]]:
matched += 1
# 如果已经找到了合法的区间,尝试缩短区间的长度
while l <= i and matched == m:
if i - l + 1 < ans_len:
flag = True
beg, end = l, i+1
ans_len = i - l + 1
# 弹出左侧元素
c = s[l]
if c in counter:
cur[c] -= 1
if cur[c] < counter[c]:
matched -= 1
l += 1
return "" if not flag else s[beg: end]
总结
上期推文: