leetcode76. 最小覆蓋子串

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

示例：

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

說明：

• 如果 S 中不存這樣的子串，則返回空字符串 ""。
• 如果 S 中存在這樣的子串，我們保證它是唯一的答案。

---

方法：滑窗

思路：

這道題要使用滑窗法，滑窗法主要就是左右兩個指針，不斷地改變窗口。

本題需要先固定左指針，滑動右指針，使得窗口覆蓋的字符串符合條件，記下此時的答案，然后滑動左指針，在符合條件的前提下，進行可能找到最短的符合條件窗口，更新答案。直到不符合條件了，再滑動右指針，直到符合條件，再滑動左指針縮小答案窗口......重復過程直到右指針抵達右邊界，此時ans存儲的最短的窗口就是答案。

這里，我們通過兩個哈希表，存儲T子串的元素情況，和S窗口中，與T相關的元素的情況，編寫一個子函數來判斷是否符合條件。

代碼：

class Solution:def minWindow(self, s: str, t: str) -> str:if not s or not t or len(s)<len(t): #排除特殊情況return ''t_need = {x:0 for x in t} temp = t_need.copy() #初始化窗口的字符情況tempfor x in t:t_need[x] += 1 #t的字符情況{字符：次數}left = right = 0 #初始化左右指針n = len(s)ans = [0,n] #初始化ans，ans表示答案窗口的左右位置，初始化為最大while right < n: #右指針擴大窗口if s[right] in temp: #擴大的這個字符是t中的，更新temptemp[s[right]] += 1 while self.compare(temp,t_need): #如果滿足條件了，開始left縮小窗口 if right-left < ans[1]-ans[0]: #窗口更小的話，更新答案ans = [left,right] if s[left] in temp: #縮小的字符在temp中，更新temptemp[s[left]] -= 1 left += 1right += 1return s[ans[0]:ans[1]+1] if ans != [0,n] else '' #最后返回答案def compare(self,x,y): #判斷是否符合條件，每個元素temp中的次數都要不小于t_needfor s in x:if x[s] < y[s]:return Falsereturn True

結果：

優化：

思路：

上面方法是否有地方可以優化呢？

答案是肯定的，上面的方法在每次判斷是否符合條件的時候，都要調用子函數，對兩個哈希表進行遍歷比較，每次比較時間復雜度達到O(N)，我們需要優化到一個常量O(1)。

我們設定一個變量distance，distance_t表示t需要的字符總數，distance表示當前窗口中t需要的字符數量，如果distance >= distance_t，那么就符合條件了，這樣就優化到一個常量比較了。但是有一個問題就是，單純的數量多不能代表符合情況，比如窗口中只有一個t中字符，但是有100個，可能也使得距離更大，但是不符合條件。

因此，對于distance，我們這么設置，在移動右指針的時候，在這個字符不滿足條件情況下，對distance+1，對于已經滿足條件的字符，pass，這樣只要distance == distance_t，那么就是符合條件的。在左指針縮小窗口時，如果查詢這個字符在s中的次數大于t需要這個字符的次數，那么還是滿足條件的，distance不用處理，如果查詢到這個字符在s中的次數等于t需要這個字符的次數，那么這個字符去掉之后，就不滿足條件了，所以將distance-1，退出循環，繼續right擴張，這就完成了使用常量來判斷狀態。

代碼：

class Solution:def minWindow(self, s: str, t: str) -> str:if not s or not t or len(s)<len(t): #排除特殊情況return ''t_need = {x:0 for x in t} temp = t_need.copy() #初始化窗口的字符情況tempdistance = 0distance_t = 0for x in t:t_need[x] += 1 #t的字符情況{字符：次數}distance_t += 1left = right = 0 #初始化左右指針n = len(s)ans = [0,n] #初始化ans，ans表示答案窗口的左右位置，初始化為最大while right < n: #右指針擴大窗口if s[right] in temp: #擴大的這個字符是t中的，更新tempif temp[s[right]] < t_need[s[right]]:distance += 1temp[s[right]] += 1 while distance == distance_t: #如果滿足條件了，開始left縮小窗口 if right-left < ans[1]-ans[0]: #窗口更小的話，更新答案ans = [left,right] if s[left] in temp: #縮小的字符在temp中，更新tempif temp[s[left]] == t_need[s[left]]:distance -= 1temp[s[left]] -= 1 left += 1right += 1return s[ans[0]:ans[1]+1] if ans != [0,n] else '' #最后返回答案

結果：

總結

以上是生活随笔為你收集整理的cstring判断是否包含子串_leetcode76. 最小覆盖子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。