76. 最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/description/
给你一个字符串 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

# a,b=input().split(",")
# a=a.strip("\"")
# b=b.strip("\"")
# a_list=list(a)
# b_list=list(b)
import copy

a_list=['D', 'K', 'A', 'F', 'W', 'A', 'D', 'C', 'B', 'E', 'I', 'L', 'B', 'C', 'E', 'A']
b_list=['B', 'C', 'A']

# a_list=['A','B','B','A','C']
# b_list=['B', 'C', 'A']

def check(A,B):
    for i in B:
        if A.count(i)<B.count(i):
            return False
    return True

def find_min(A,B):
    i,j=0,0
    flag=False
    temp=[]
    while i<=len(A) and j<=len(A):
        while(flag==False ):
            j=j+1
            flag=check(A[i:j],B)
            if j>len(A):
                return temp
        temp.append(A[i:j])
        while(flag==True ):
            i=i+1
            flag=check(A[i:j],B)
            if i==len(A):
                return temp
        temp.append(A[i-1:j])

    return temp


def procese(A,B):
    temp=find_min(A,B)
    min_len=100000000
    for i in temp:
        if min_len>=len(i):
            min_len=len(i)
    for i in temp:
        if len(i)==min_len:
            return i

def main():
    a,b=input().split(",")
    a=a.strip("\"")
    b=b.strip("\"")
    a_list=list(a)
    b_list=list(b)
    return procese(a_list,b_list)

if __name__ == '__main__':
   out=main()
   print("\"",end="")
   try:
    for i in out:
        print(i, end="")
   except:
        pass
   print("\"", end="")
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67