LeetCode刷题实战76：最小覆盖子串
共 2636字，需浏览 6分钟
·
2020-10-25 02:29
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从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 中存在这样的子串，我们保证它是唯一的答案。
解题
分析
，然而我们遍历字符串的复杂度就已经是了，也就是说我们不能引入额外的计算开销，否则一定不满足题目的要求。时间内判断字符串匹配的KMP算法，如果你不知道这个算法也没有关系，因为这个算法并不适用。因为我们要找的不是完全相等的子串的位置，而是找的是字符构成一样的子串，所以并不能通过引入字符串匹配算法来解决。没有学过KMP算法的同学可以松一口气了，这题当中并不会引入新的算法。解题的套路
。我们的目标是寻找子串，也就是说我们遍历的过程应该对应一个子串，并且我们有方法可以快速判断这个子串是否合法。这样我们才可以做到遍历的同时判断答案的可行性。进而可以想到这是一个区间维护的问题，区间维护我们经常使用的方法就是two pointers。所以我们可以试试two pointers能否适用。题解
# 存储区间内的字符
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]
总结
的算法呢？的算法。上期推文：