76. 最小覆盖子串 [hard]

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

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

通过次数66,271提交次数172,817

First Try

2020-08-02

使用移动窗口，右边指针已经覆盖完目标字符串后，由于可能存在多余的字符，因此移动左边指针不断缩小窗口，看什么时候不再匹配。在这里面的最后一步就是右指针覆盖范围内的最小范围。然后再继续移动右边指针，重复这个过程。把一个O(N^2)的算法，变成了O(N)级别。

但是在比较字符串是否匹配相等的时候，对counter进行遍历，每前进一步都要比较一次，感觉浪费得太严重了, 这也是时间排名靠后的原因。

counter比较里一个容易出错的地方：只要统计值比target值大，就可以认为符合要求，并不要求数量一定要相等。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        
        def counter_eq(target_c, c):
            for k, v in target_c.items():
                # if c[k] != v: # 不是相等，而是数量比对方大即可。。
                if c[k] < v:
                    return False 
            return True 

        target = collections.Counter(t)
        counter = collections.Counter()
        ns, nt = len(s), len(t)
        i, j = 0, 0  
        rv = []

        while  i < ns - nt + 1 and j < ns:
            while j < ns and not counter_eq(target, counter):
                counter[s[j]] += 1 
                j += 1
            while i < ns - nt + 1 and counter_eq(target, counter):
                rv.append([i, j - 1])  # 注意j不符合，必须是j - 1
                counter[s[i]] -= 1 
                i += 1
        if not len(rv):
            return ""
        rv = min(rv, key = lambda x: x[1] - x[0])
        return s[rv[0]: rv[1] + 1]

执行用时：512 ms, 在所有 Python3 提交中击败了20.95%的用户
内存消耗：27.4 MB, 在所有 Python3 提交中击败了5.10%的用户

Failed Try

2020-07-29

测试案例: "a", "aa" -> 要求输出为"", 也就是对target中的字符数量有要求，又是题意混乱。。

O(N^2)暴力法来一波,果然超时了。。。

从(0, n)开始遍历，计算得到的符合的长度，必然包括了结果，但是也多次重复计算。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 暴力法来一个？  超时的测试集 s为100k字符，t为10k个字符
        target = collections.Counter(t)
        ns, nt = len(s), len(t)
        print(ns, nt)
        seq = []
        i = 0 
        min_gap = float('inf')
        while i < ns - nt + 1:
            if s[i] in target:
                j = i 
                counter = collections.Counter(target)
                while j < ns:
                    if j - i > min_gap:
                        break 
                    if s[j] in counter:
                    # if s[j] in target:  # 又是一个bug, 要么判断的时候u 就不要用==0，而用<=0
                        counter[s[j]] -= 1 
                        if counter[s[j]] == 0:
                            counter.pop(s[j])
                        if len(counter) == 0:
                            seq.append([i, j])
                            min_gap = min(min_gap, j - i)
                            break 
                    j += 1
            i += 1
        if not len(seq):
            return ""
        i, j = min(seq, key = lambda x: x[1] - x[0])
        return s[i: j + 1]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 先找第一个，然后再不断移动缩小？
        # 暴力法来一个？
        # 测试案例: "a", "aa" -> 要求输出为"" t里面的数量原来也是需要的，又是题意混乱。。
        target = set(t)
        ns, nt = len(s), len(target)
        seq = []
        i = 0 
        while i < ns:
            if s[i] in target:
                j = i 
                counter = collections.defaultdict(int)
                while j < ns:
                    if s[j] in target:
                        counter[s[j]] += 1 
                        if len(counter.keys()) == nt:
                            seq.append([i, j])
                            break 
                    j += 1
            i += 1
        if not len(seq):
            return ""
        i, j = min(seq, key = lambda x: x[1] - x[0])
        return s[i: j + 1]

76. 最小覆盖子串 [hard]​

First Try​

Failed Try​

76. 最小覆盖子串 [hard]

First Try

Failed Try