76. 最小覆盖子串

思路：不断的滑动窗口，判断子串包不包含t即可。但是我这个判断包含不包含这个逻辑写的太简单了，以至于下面这种情况把我恶心住了。理论上这种情况不应该移动窗口，直接baa，需要优化。

还是我过于年轻 明天再战

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        '''
        滑动窗口 判断窗口是否包含t即可 
        '''
        def judge(_s,t):
            '''
            判断s包含不包含t
            '''
            if len(s) < len(t): # s 比 t 元素少 不可能包含t
                return False
       
            for i in t:
                if i not in _s:
                    return False
            return True

        # 判断s包含不包含t 不包含自己返回即可
        if not judge(s,t):
            return ''
        if s==t:
            return s
            
        # s包含t 寻找最小子串
        i,j = 0,0 # 窗口起始位置、结束为止
        _s = '' 
        res = s # 最小子串
        while j < len(s):
            _s += s[j]
            j += 1
            while judge(_s,t):  # s中包含t了
                res = _s if len(_s) < len(res) else res # 结果是一个子串
                i += 1 # 窗口向前移动
                _s,j = '',i
                
        return res 

进一步优化后 考虑到子串长度必须>=t
于是有了

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        '''
        滑动窗口 判断窗口是否包含t即可 
        '''
        def judge(_s,t):
            '''
            判断s包含不包含t
            '''
            if len(s) < len(t): # s 比 t 元素少 不可能包含t
                return False
       
            for i in t:
                if i not in _s:
                    return False
            return True

        # 判断s包含不包含t 不包含自己返回即可
        if not judge(s,t):
            return ''
        if s==t:
            return s

        # s包含t 寻找最小子串
        i,j = 0,0 # 窗口起始位置、结束为止
        _s = '' 
        res = s # 最小子串
        while j < len(s):
            _s += s[j]
            j += 1
            while judge(_s,t):  # s中包含t了
                res = _s if len(_s) < len(res) and len(_s) >= len(t) else res # 结果是一个子串
                i += 1 # 窗口向前移动
                _s,j = '',i
                
        return res 

参考链接

    def minWindow(self, s: str, t: str) -> str:
        need=collections.defaultdict(int)
        for c in t:
            need[c]+=1
        needCnt=len(t)
        i=0
        res=(0,float('inf'))
        for j,c in enumerate(s):
            if need[c]>0:
                needCnt-=1
            need[c]-=1
            if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
                while True:      #步骤二：增加i，排除多余元素
                    c=s[i] 
                    if need[c]==0:
                        break
                    need[c]+=1
                    i+=1
                if j-i<res[1]-res[0]:   #记录结果
                    res=(i,j)
                need[s[i]]+=1  #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
                needCnt+=1
                i+=1
        return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果

作者：Mcdull0921
链接：https://leetcode-cn.com/problems/minimum-window-substring/solution/tong-su-qie-xiang-xi-de-miao-shu-hua-dong-chuang-k/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。