#76 Minimum Window Substring——Top 100 Liked Questions

野性酷女 2022-01-27 01:57 164阅读 0赞

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

**Example:**

Input: S = "ADOBECODEBANC", T = "ABC"
    Output: "BANC"

**Note:**

*  If there is no such window in S that covers all characters in T, return the empty string `""`.
 *  If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

> """
> 
> 第一次：移动窗口法：设置left和right两个指针，当t的字符没有全都包含在窗口（left与right之间）中时，向右移动right， 当窗口中包含t时，此时向右移动left指针，每移动一次left，判断此时窗口是否还包含t，当包含时，left指针继续右移，否则记录此时left与right的位置，与保存窗口信息的res比较，更新最短窗口信息。主要思考：怎么验证窗口中否全都包含了t？采用字典，记录每个字母出现的次数，看t中字母出现的次数是否与窗口中的次数相同！  
> """
> 
> from collections import Counter  
> class Solution(object):  
>     def minWindow(self, s, t):  
>         """  
>         :type s: str  
>         :type t: str  
>         :rtype: str  
>         """  
>         if not s or not t:  
>             return ""  
>         Ls = len(s)  
>         left, right = 0, 0  
>         res = float("inf"), left, right  
>         sWindowCount = \{\}  
>         tCount = Counter(t)        flag = 0  
>         while right < Ls:  
>             sWindowCount\[s\[right\]\] = sWindowCount.get(s\[right\], 0) + 1  
>             if s\[right\] in tCount and sWindowCount\[s\[right\]\] == tCount\[s\[right\]\]:  
>                 flag += 1  
>             while flag == Ltc and left <= right:  
>                 if right - left + 1 < res\[0\]:  
>                     res = right - left + 1, left, right  
>                 sWindowCount\[s\[left\]\] -= 1  
>                 if s\[left\] in tCount and sWindowCount\[s\[left\]\] < tCount\[s\[left\]\]:  
>                     flag -= 1  
>                 left += 1  
>             right += 1  
>         return "" if res\[0\] == float("inf") else s\[res\[1\]: res\[2\] + 1\]
> 
> """
> 
> Runtime: 116 ms, faster than 65.73% of Python online submissions forMinimum Window Substring.
> 
> Memory Usage: 12.4 MB, less than 93.71% of Python online submissions forMinimum Window Substring.
> 
> """