【Day 46 】2024-05-23 - 76. 最小覆盖子串

[azl397985856]

76. 最小覆盖子串

入选理由

暂无

题目地址

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

前置知识

• Sliding Window
• 哈希表

  题目描述

  
  给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

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

提示：

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

[lxy1108]

思路

滑动窗口，每次发现有可以覆盖t的s子窗口时，对窗口进行收紧从而得到最短的子窗口

python3代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_arr = collections.defaultdict(int)
        for ch in t:
            t_arr[ch]+=1
        def ifcover(cur_arr):
            for k in t_arr:
                if cur_arr[k]<t_arr[k]:
                    return False
            return True
        cur_arr = collections.defaultdict(int)
        rs = ""
        start=0
        end=start+1
        while start<len(s):
            while end<=len(s):
                cur_arr[s[end-1]]+=1
                if ifcover(cur_arr):
                    break
                end+=1
            if not ifcover(cur_arr):
                return rs
            while start<end and cur_arr[s[start]]-1>=t_arr[s[start]]:
                cur_arr[s[start]]-=1
                start+=1
            if rs=="" or end-start<len(rs):
                rs = s[start:end]
            cur_arr[s[start]]-=1
            start+=1
            end+=1
        return rs

[luzhaofeng]

class Solution:
    def minWindow(self, s: str, t: str) -> str:

        if len(t) > len(s):
            return ''        

        cnt = collections.Counter(t)   
        need = len(t)                   

        n = len(s)
        start, end = 0, -1         
        min_len = n + 1             
        left = right = 0           
        for right in range(n):

            # 窗口右边界右移一位
            ch = s[right]             
            if ch in cnt:               
                if cnt[ch] > 0:         
                    need -= 1          
                cnt[ch] -= 1

            # 窗口左边界持续右移
            while need == 0:            
                if right - left + 1 < min_len:     
                    min_len = right - left + 1
                    start, end = left, right

                ch = s[left]            
                if ch in cnt:           
                    if cnt[ch] >= 0:    
                        need += 1      
                    cnt[ch] += 1
                left += 1              

        return s[start: end+1]

[Hermione666]

class Solution: def minWindow(self, s: str, t: str) -> str:

Initialize variables

    m, n = len(s), len(t)

    # If s is shorter than t, return empty string
    if m < n:
        return ""

    # Create dictionaries to count characters in t and the current window in s
    dictt = {}
    for char in t:
        if char in dictt:
            dictt[char] += 1
        else:
            dictt[char] = 1

    dicts = {}

    # Initialize the window pointers and variables to track the minimum window
    left, right = 0, 0
    required = len(dictt)
    formed = 0
    min_len = float('inf')
    ans = ""

    while right < m:
        # Add characters from the right end to the current window
        char = s[right]
        if char in dicts:
            dicts[char] += 1
        else:
            dicts[char] = 1

        # Check if the current character makes the window valid
        if char in dictt and dicts[char] == dictt[char]:
            formed += 1

        # Try to contract the window from the left until it's no longer valid
        while left <= right and formed == required:
            char = s[left]

            # Update the minimum window
            if right - left + 1 < min_len:
                min_len = right - left + 1
                ans = s[left:right + 1]

            # Remove the leftmost character from the window
            dicts[char] -= 1
            if char in dictt and dicts[char] < dictt[char]:
                formed -= 1

            left += 1

        # Move the right end of the window to the right
        right += 1

    return ans

[zhiyuanpeng]

from collections import Counter
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        td = Counter(t)
        wd = Counter()
        tl = len(td)
        ans = ""
        ans_len = float("inf")
        j = 0
        k = 0
        for i in range(len(s)):
            wd[s[i]] += 1
            if wd[s[i]] == td[s[i]]:
                k += 1
            while k == tl:
                if i-j+1 < ans_len:
                    ans_len = i-j+1
                    ans = s[j: i+1]
                wd[s[j]] -= 1
                if wd[s[j]] == td[s[j]] - 1:
                    k -= 1
                j += 1
        return ans

[Dtjk]

class Solution: def minWindow(self, s: 'str', t: 'str') -> 'str': from collections import Counter t = Counter(t) lookup = Counter() start = 0 end = 0 min_len = float("inf") res = "" while end < len(s): lookup[s[end]] += 1 end += 1

print(start, end)

        while all(map(lambda x: lookup[x] >= t[x], t.keys())):
            if end - start < min_len:
                res = s[start:end]
                min_len = end - start
            lookup[s[start]] -= 1
            start += 1
    return res