Skip to content

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]


回到顶部