[LeetCode]76 最小覆盖子串

题目描述

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例:

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

代码

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
from collections import defaultdict
class Solution:
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        mem = defaultdict(int)
        for c in t:
            mem[c] += 1
        t_len = len(t)
        
        minL, minR = 0, float('inf')
        
        l = 0
        for r, c in enumerate(s):
            if mem[c] > 0:
                t_len -= 1
            mem[c] -= 1
                
            if t_len == 0:
                while mem[s[l]] < 0:
                    mem[s[l]] += 1
                    l += 1
                    
                if r - l < minR - minL:
                    minL, minR = l, r
                
                mem[s[l]] += 1
                t_len += 1
                l += 1
        
        return '' if minR == float('inf') else s[minL:minR+1]