?LeetCode刷題實(shí)戰(zhàn)76：最小覆蓋子串
算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問(wèn)題叫做?最小覆蓋子串，我們先來(lái)看題面：
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 中存在這樣的子串，我們保證它是唯一的答案。
解題
分析
，然而我們遍歷字符串的復(fù)雜度就已經(jīng)是了，也就是說(shuō)我們不能引入額外的計(jì)算開(kāi)銷(xiāo)，否則一定不滿(mǎn)足題目的要求。時(shí)間內(nèi)判斷字符串匹配的KMP算法，如果你不知道這個(gè)算法也沒(méi)有關(guān)系，因?yàn)檫@個(gè)算法并不適用。因?yàn)槲覀円业牟皇峭耆嗟鹊淖哟奈恢茫钦业氖亲址麡?gòu)成一樣的子串，所以并不能通過(guò)引入字符串匹配算法來(lái)解決。沒(méi)有學(xué)過(guò)KMP算法的同學(xué)可以松一口氣了，這題當(dāng)中并不會(huì)引入新的算法。解題的套路
。我們的目標(biāo)是尋找子串，也就是說(shuō)我們遍歷的過(guò)程應(yīng)該對(duì)應(yīng)一個(gè)子串，并且我們有方法可以快速判斷這個(gè)子串是否合法。這樣我們才可以做到遍歷的同時(shí)判斷答案的可行性。進(jìn)而可以想到這是一個(gè)區(qū)間維護(hù)的問(wèn)題，區(qū)間維護(hù)我們經(jīng)常使用的方法就是two pointers。所以我們可以試試two pointers能否適用。題解
# 存儲(chǔ)區(qū)間內(nèi)的字符
segement = {}
for?i in?range(n):
????segement[s[i]] += 1
????# 當(dāng)滿(mǎn)足條件的時(shí)候移動(dòng)區(qū)間左側(cè)
????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
????????# 通過(guò)Counter直接獲取T當(dāng)中的字符構(gòu)成
????????counter = Counter(t)
????????n, m = len(s), len(counter)
????????l, beg, end = 0, 0, 0
????????cur = defaultdict(int)
????????matched = 0
????????flag = False
????????# 記錄合法的字符串的長(zhǎng)度
????????ans_len = 0x3f3f3f3f
????????
????????for?i in?range(n):
????????????if?s[i] not?in?counter:
????????????????continue
????????????????
????????????cur[s[i]] += 1
????????????# 當(dāng)數(shù)量匹配上的時(shí)候，matched+1
????????????if?cur[s[i]] == counter[s[i]]:
????????????????matched += 1
????????????????
????????????# 如果已經(jīng)找到了合法的區(qū)間，嘗試縮短區(qū)間的長(zhǎng)度
????????????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è)元素
????????????????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]
總結(jié)
的算法呢？的算法。上期推文：