?LeetCode刷題實戰(zhàn)76：最小覆蓋子串
算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?最小覆蓋子串，我們先來看題面：
https://leetcode-cn.com/problems/minimum-window-substring/
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).
題意
輸入：S = "ADOBECODEBANC", T = "ABC"
輸出："BANC"
提示：
如果 S 中不存這樣的子串，則返回空字符串 ""。
如果 S 中存在這樣的子串，我們保證它是唯一的答案。
解題
分析
，然而我們遍歷字符串的復雜度就已經是了，也就是說我們不能引入額外的計算開銷，否則一定不滿足題目的要求。時間內判斷字符串匹配的KMP算法，如果你不知道這個算法也沒有關系，因為這個算法并不適用。因為我們要找的不是完全相等的子串的位置，而是找的是字符構成一樣的子串，所以并不能通過引入字符串匹配算法來解決。沒有學過KMP算法的同學可以松一口氣了，這題當中并不會引入新的算法。解題的套路
。我們的目標是尋找子串，也就是說我們遍歷的過程應該對應一個子串，并且我們有方法可以快速判斷這個子串是否合法。這樣我們才可以做到遍歷的同時判斷答案的可行性。進而可以想到這是一個區(qū)間維護的問題，區(qū)間維護我們經常使用的方法就是two pointers。所以我們可以試試two pointers能否適用。題解
# 存儲區(qū)間內的字符
segement = {}
for?i in?range(n):
????segement[s[i]] += 1
????# 當滿足條件的時候移動區(qū)間左側
????while?l <= i and?satisified(segment):
????????# 更新最佳答案
????????if?i - l + 1?< ans_len:
????????????ans_len = i - l + 1
????????????beg, end?= l, i + 1
????????# 彈出元素
??segement[s[l]] -= 1
????????l += 1
class?Solution:
????def?minWindow(self, s: str, t: str)?-> str:
????????from?collections import?Counter, defaultdict
????????# 通過Counter直接獲取T當中的字符構成
????????counter = Counter(t)
????????n, m = len(s), len(counter)
????????l, beg, end = 0, 0, 0
????????cur = defaultdict(int)
????????matched = 0
????????flag = False
????????# 記錄合法的字符串的長度
????????ans_len = 0x3f3f3f3f
????????
????????for?i in?range(n):
????????????if?s[i] not?in?counter:
????????????????continue
????????????????
????????????cur[s[i]] += 1
????????????# 當數(shù)量匹配上的時候，matched+1
????????????if?cur[s[i]] == counter[s[i]]:
????????????????matched += 1
????????????????
????????????# 如果已經找到了合法的區(qū)間，嘗試縮短區(qū)間的長度
????????????while?l <= i and?matched == m:
????????????????if?i - l + 1?< ans_len:
????????????????????flag = True
????????????????????beg, end = l, i+1
????????????????????ans_len = i - l + 1
????????????????????
????????????????# 彈出左側元素
????????????????c = s[l]
????????????????if?c in?counter:
????????????????????cur[c] -= 1
????????????????????if?cur[c] < counter[c]:
????????????????????????matched -= 1
????????????????????????
????????????????l += 1
????????
????????return?""?if?not?flag else?s[beg: end]
總結
的算法呢？的算法。上期推文：