76. Minimum Window Substring

Loading...LeetCode

在S中找包含T的substring，暴力搜索没法把时间复杂度控制在O(n)，还是sliding window，跟 3. Longest Substring Without Repeating Characters 相比只是变成了window跟T的比较，而非检查重复。所以基本上还是移动左右指针 i, j 然后检查 window.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target = collections.Counter(t)
            
        match = 0
        res = ""
        minL = len(s)+1
        
        l, r = 0, 0
        while r < len(s):
            
            target[s[r]] -= 1
            if target[s[r]] >= 0: 
                match += 1
            
            while match == len(t):
                if r+1-l <= minL: 
                        res = s[l:r+1]
                        minL = len(res)
                
                target[s[l]] += 1
                if target[s[l]] > 0:
                    match -= 1
                l += 1
            
            r += 1
            
        return res

这边有个优化，就是可以不用滑过整个S，只需要把S里面出现的T元素挑出来，然后用window左右边界跳跃式地滑在这些元素上，没出现在T里面的元素，可以直接跳过不看。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 整理目标count
        # 最终目的是让target成为结果freq的子集，那可以直接维护这一个target对象
        target = dict()
        for c in t:
            target[c] = target.get(c, 0) + 1
        
        # 左指针移动条件：找到一个结果 => match数量达到len(t)
        # 记录结果条件：找到一个结果 => match数量达到len(t)、新结果比旧结果短 => len(substring) < len(res)
        # 所以先初始化这两个值
        match = 0
        res = ''
        minL = len(s)+1
        
        l, r = 0, 0
        while r < len(s):
            # 当前字符是需要匹配的，match++
            if s[r] in target.keys() and target[s[r]] > 0:
                match +=1
            # 匹配好之后，把“待匹配值”--
            target[s[r]] = target.get(s[r], 0) - 1
            
            # 左指针移动条件 & 记录结果条件[0]
            while match == len(t):
                # 记录结果条件[1]
                if r+1 - l < minL:
                    res = s[l:r+1]
                    minL = len(res)
                
                # 因为左指针要移动了，最左端的字符匹配需要加回目标库
                target[s[l]] = target.get(s[l], 0) + 1
                # 如果最左是该字符的唯一匹配，那match也要--
                if target[s[l]] > 0:
                    match -= 1
                l += 1
            
            # 移动右指针，继续扫描
            r += 1
            
        return res