076 Minimum Window Substring
76. Minimum Window Substring
题目： https://leetcode.com/problems/minimum-window-substring/
难度 : Hard
模板大法
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
if len(t) > len(s):
return ''
maps = collections.Counter(t)
counter = len(maps.keys())
begin, end, head, length = 0, 0, 0, float('inf')
while end < len(s):
if s[end] in maps:
maps[s[end]] -= 1
if maps[s[end]] == 0:
counter -= 1
end += 1
while counter == 0:
if s[begin] in maps:
maps[s[begin]] += 1
if maps[s[begin]] > 0:
counter += 1
if end - begin < length:
length = end - begin
head = begin
begin += 1
if length == float('inf'):
return ''
return s[head:head+length]
