[LeetCode]76. 最小覆盖子串(Minimum Window Substring)

题目描述

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。

示例:

输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”

说明:

  • 如果 S 中不存这样的子串,则返回空字符串 “”。
  • 如果 S 中存在这样的子串,我们保证它是唯一的答案。

解题思路

使用滑动窗口,用两个指针,right 指针用来不断扩张窗口,left 指针用来压缩窗口得到更好的结果。通过移动 right 指针不断扩张窗口,当满足所有字符的条件之后,如果可以收缩,则移动 left 指针收缩窗口,若收缩后使得窗口不满足条件,则继续移动 right 指针扩张窗口,只需记录下来最小的窗口的结果即可。

代码

Python 2.7.12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
if not t or not s:
return ""
char_count = {} # 存储 t 中字符的频数
for char in t:
char_count[char] = char_count.get(char, 0) + 1
required = len(char_count) # t 中不重复的字符数
formed = 0 # 用来存储目前 window 中的满足要求的唯一字符数,与 required 比较
window_count = {} # 用来存储目前 window 中所有字符的频数
l, r = 0, 0
ans = (float("inf"), None, None) # 用来存储满足条件的结果:(window length, left index, right index)
while r < len(s):
char = s[r]
window_count[char] = window_count.get(char, 0) + 1
if char in char_count and window_count[char] == char_count[char]:
# 如果刚进 window 的这个字符是 t 中的且频数一致,则 formed + 1
formed += 1
while l <= r and formed == required:
# 如果当前 window 满足所有要求,则压缩 window 看是否能得到更小的结果
char = s[l]
if r - l + 1 < ans[0]:
ans = (r - l + 1, l, r)
window_count[char] -= 1
if char in char_count and window_count[char] < char_count[char]:
formed -= 1
l += 1
r += 1
return "" if ans[1] is None else s[ans[1]:ans[2] + 1]

执行用时 : 92 ms
内存消耗 : 12.6 MB

参考

https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-2