给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
1
2
3
4
5
6
7
|
输入:
S = "ADOBECODEBANC", T = "ABC"
输出:
"BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class (object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
from collections import Counter
dic = Counter(t)
start = 0
end = 0
length = sys.maxsize
window = Counter()
ans = ""
while end < len(s):
window[s[end]] += 1
while all(map(lambda x: window[x] >= dic[x] , dic.keys())):
if end-start < length:
length = end-start+1
ans = s[start: end+1]
window[s[start]] -= 1
start += 1
end += 1
return ans
|
近期评论