76. Minimum Window Substring
給你兩個 string s and t 問你能讓 t 的每個字元都出現的 s 的最短 substring
t 會包含 duplicate characters
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Example 2:
Input: s = "a", t = "a"
Output: "a"
Example 3:
Input: s = "a", t = "aa"
Output: ""
思路:
1.因為 substring 是連續的可以用左界右界去檢查 如果 t 不會重複就簡單了
維護一個 set 和 set(t), left right 都從 0 開始
如果目前子字串合法就推進 left 反之推進 right
推進 left 的意思: 拔掉 s[left], 檢查 s[left] 有沒有在 set(t) 裡 有就拔掉
推進 right 的意思: 加進 s[right], 檢查 s[right] 有沒有在 set(t) 裡 有就加
合不合法就是看目前 set 的長度有沒有跟 set(t) 的長度一樣
2.但是 t 會重複 所以改用 dict 概念還是差不多就是
這裡要再開一個 dict 去和 dict(t) 比較也是可以 只是 code 會變得很長
所以稍微改變一下 dict 的意思 不是字元目前出現的數量 而是還缺多少個
這樣就能算完 t 的數量之後把 tdict = Counter(t) 直接拿來用
另外檢查合不合法也多開一個變數去記 意思也是目前差多少個目標字元 tlen = len(t)
推進 left: tdict[s[left]] += 1 意思是拔掉 s[left] 後他的需求數量變多了
tlen += (tdict[s[left]] > 0) 如果拔掉會讓他的需求超過 1 就加上去
這裡要多檢查是因為有些 s 的字元一開始不會出現在 tdict 中
所以要想辦法在更新 tlen 的時候忽略掉他們 而因為字元一定是先被 right 碰到
也就是先加入後移除 所以一開始不在 tdict 當中的字元 他的需求數量一定是 <= 0
這種字元我們在更新 tlen 時就不用理他了 不會影響合不合法
最後 怎麼檢查合不合法? 就是看 tlen 等不等於 0
Python code:
class Solution:
def minWindow(self, s: str, t: str) -> str:
n, tdict, tlen = len(s), Counter(t), len(t)
left, right = 0, 0
res, reslen = "", float('inf')
while r <= n:
if tlen == 0:
if r-l+1 < reslen:
res = s[l:r]
reslen = r-l+1
tdict[s[l]] += 1
tlen += (tdict[s[l]] > 0)
l += 1
else:
if r == n:
break
tdict[s[r]] -= 1
tlen -= (tdict[s[r]] >= 0)
r += 1
return res
單迴圈版本 寫完覺得跟班長一樣醜
再參考一下別人的 iterate 右界 推進左界直到不合法
class Solution:
def minWindow(self, s: str, t: str) -> str:
n, tdict, tlen = len(s), Counter(t), len(t)
left, right = 0, 0
res, reslen = "", float('inf')
for right in range(n):
tlen -= tdict[s[right]] > 0
tdict[s[right]] -= 1
while tlen == 0:
if right-left < reslen:
res = s[left:right+1]
reslen = right-left
tdict[s[left]] += 1
tlen += tdict[s[left]] > 0
left += 1
return res
有稍微順眼一點了

288