Python solution greedy


  • 0
    Z
    class Solution(object):
        def minWindow(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: str
            """
            last_dict = {}
            for tc in t:
                last_dict.setdefault(tc,[])
                last_dict[tc].append(float('-inf'))
            start, end = float('-inf'), 0
            min_start, min_end = float('-inf'), float('inf')
            while end < len(s):
                if s[end] in last_dict:
                    last_dict[s[end]][0] = end
                    last_dict[s[end]].sort()
                    farthest_char = min(last_dict.items(), key = lambda t: t[1][0])
                    start = farthest_char[1][0]
                    if min_end - min_start > end - start or min_start < 0:
                        min_end, min_start = end, start
                end += 1
            if min_start >= 0:
                return s[min_start:min_end+1]
            return ''```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.