Leetcode 76. Minimum Window Substring 最小覆寫子串

标簽：

Leetcode

題目位址：https://leetcode-cn.com/problems/minimum-window-substring/

題目描述

給你一個字元串 S、一個字元串 T，請在字元串 S 裡面找出：包含 T 所有字母的最小子串。

示例：

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

說明：

• 如果 S 中不存這樣的子串，則傳回空字元串

  ""

  。
• 如果 S 中存在這樣的子串，我們保證它是唯一的答案。

算法思想

這個問題是在一個大的字元串裡面找小的字元串，是以可以考慮使用滑動視窗來做。并且我們對待比對的字元串并不關心字元的前後位置，隻關心字元個數，是以可以用hash表把字元情況存儲起來，等到周遊的時候進行更新。

我們用

left right

代表滑動視窗的左邊和右邊，用

m

代表目标字元串中的資料情況，

count

代表目前比對的長度。保證視窗的右邊不超過字元串的長度即可。周遊的時候我們先看目前周遊到的字元是否在m中，如果在的話，需要更新m，并且根據m中對應字元的大小，來确定目前是否需要更新

count

。如果我們的

m[s[right]]>=0

則需要更新count，否則不更新（因為如果<0 則代表目标子串中對應的這個字元早已比對完了，是以即使再有多的也無用）。

最後根據count和目标子串比較，如果相等，說明目前比對成功，是以和以前的長度比較，更新。同時也要更新

left

，同樣這裡會有一個對

m[s[left]] > 0

的判斷，這個類似上面的right，因為如果

>0

則代表把重複的用完了，下面再用的話就真的用到了目标串裡面的了，是以下面需要更新

count

。

python代碼

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        left,right= 0,0
        minLen = len(s)+1 # 初始化的時候為最大，這樣後面能更新
        m = {}
        res = ""
        for i in t:
            m[i] = m.get(i,0) + 1# 因為隻是要統計t中出現字元，不需要順序一緻，是以可以用hash存儲
        # 開始滑動視窗先找右，再滑動左
        count = 0 # 表示t中有多少個在s中，不包括s中多的重複的
        while right<len(s):
            if s[right] in m:
                m[s[right]] -=1 # 比對掉了
                if m[s[right]]>=0:# 必須要>=0  比如 ABBBC 和ABC 當比對到第一個B的時候count需要+=1，但是第二個的時候m["B"] = -1此時不需要count+=1了，因為重複了
                    count+=1
                while count == len(t): # 說明這個視窗裡面包含了所有
                    if right -left + 1<minLen:
                        minLen = right -left + 1
                        res = s[left:right+1]
                    if s[left] in m: # 滑動left之前先看這個被滑動的是不是會影響count
                        m[s[left]] +=1
                        if m[s[left]] > 0 : # 說明滑動到了最後一個，把之前囤積的都滑動沒了,對count更新
                            count -=1
                    left +=1
            right +=1
        return res

           

參考：

https://blog.csdn.net/weixin_41958153/article/details/81623474

歡迎大家關注我的微信公衆号，未來上面會推送

python

機器學習

算法學習

深度學習

論文閱讀

以及偶爾的

小雞湯

等内容。ようこそいらっしゃい！

搜尋 coderwangson 關注