【LeetCode】0076 最小覆盖子串

https://leetcode-cn.com/problems/minimum-window-substring/

# -*- coding:utf-8 -*-

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        weight_list = []
        str_list = []
        temp_weight = 0
        for i in range(len(s)):
            if s[i] not in t:
                temp_weight += 1
                continue
            temp_weight += 1
            str_list.append(s[i])
            weight_list.append(temp_weight)
            temp_weight = 0
        windows_length = len(t)
        current_min_idx = -1
        current_min_val = float('inf')
        for i in range(len(str_list) - windows_length + 1):
            queue = []
            temp_val = 0
            for j in range(windows_length):
                if len(queue) != len(t) and str_list[i + j] not in queue:
                    queue.append(str_list[i + j])
                    if j != 0:
                        temp_val += weight_list[i + j]
                    else:
                        temp_val += 1
                if len(queue) == len(t):
                    if temp_val < current_min_val:
                        current_min_idx = i
                        current_min_val = temp_val
        if current_min_idx == -1:
            return ''
        from_idx = 0
        for i in range(current_min_idx + 1):
            from_idx += weight_list[i]
        return s[from_idx - 1:from_idx + current_min_val - 1]
if __name__ == '__main__':
    S = "aa"
    T = "aa"
    # S = "ADOBECODEBANC"
    # T = "ABC"
    print(Solution().minWindow(S, T))

思路：这道题我感觉我思路挺好的，复杂度应该。。？我也不知道多少，最坏n^2应该是。

首先就是把无关字符全去掉，比如ADOBECODEBANC直接过滤成ABCBAC，然后每一个字母都带一个权重，代表当前字母后n个长度为下一个t中的字符，比如ABCBAC对应一个权重就是1，3，2，4，1，2。因此问题就变成了找最短权重的一个字符串。

我们利用一个t长度的窗口，判断窗口内是不是t中的字符，然后算一下权重，找到权重最低的窗口，根据权重就可以映射到原字符串的索引范围。

上面代码中使用的是列表进行重复判断，但是实际上t是允许重复的，那么我们把列表变成字典，多循环一遍t就可以了。太懒了就不写了，但是思路肯定是对的，对不起对不起对不起对不起，今天出门一天，晚上才回来，实在是不想改这点代码了。