解題思路
滑動窗口可用于解決一些列的字符匹配問題，典型的問題包括：在字符串 sss 中找到一個最短的子串，使得其能覆蓋到目標字符串 ttt。對于目標字符串 ttt，我們可以在字符串 sss 上滑動窗口，當窗口包含 ttt 中的全部字符后，我們再根據(jù)題意考慮能否收縮窗口。
在窗口滑動的過程中，我們可以暴力地統(tǒng)計出窗口中所包含的字符是否滿足題目要求，但這沒有利用到滑動窗口的基本性質(zhì)。事實上，窗口的滑動過程可分解為以下兩步基礎操作：
- 窗口右邊界往右滑動一位：窗口右端新加入一個字符，但窗口中的其他字符沒有發(fā)生變化；
- 窗口左邊界往右滑動一位：窗口左端滑出一個字符，但窗口中的其他字符沒有發(fā)生變化。
因此，我們可以考慮在「一進一出」這樣的兩個基礎操作上做文章。
基于滑動窗口，可解決一系列字符串匹配問題，下面以幾個同類的題目為例：
變長滑動窗口：字符串
題解：https:///problems/minimum-window-substring/solution/by-flix-1kac/
題解：https:///problems/M1oyTv/solution/by-flix-4bcr/
題目回顧：
給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 。
注意：
對于 t 中重復字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。
如果 s 中存在這樣的子串，我們保證它是唯一的答案。
示例 1：
輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"
示例 2：
輸入：s = "a", t = "a"
輸出："a"
示例 3:
輸入: s = "a", t = "aa"
輸出: ""
解釋: t 中兩個字符 'a' 均應包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 10^5
s 和 t 由英文字母組成
解題思路：
上述兩個題目是一樣的，我們以哈希表 cntcntcnt 記錄目標字符串 ttt 中待匹配的各字符的數(shù)目，并在 sss 中維護一個變長的滑動窗口，期望使得窗口中的字符能夠覆蓋 ttt。需要注意的是，cnt[ch]cnt[ch]cnt[ch] 可以為負值，且負值表示當前窗口中的字符 chchch 過多（多于目標字符 ttt）。
具體地，設定一個非負變量 needneedneed 表示在考慮了窗口中的全部元素后還需要匹配的總字符數(shù)目：
-
當窗口中新加入一位字符 chchch 時：
- 若 cnt[ch]>0cnt[ch]>0cnt[ch]>0，說明 chchch 未加入窗口前我們對于字符 chchch 還有需求，此時新加入的 chchch 能夠使得 need?1need-1need?1；
- 若 cnt[ch]≤0cnt[ch]\leq0cnt[ch]≤0，說明 chchch 未加入窗口前我們對于字符 chchch 已無需求，此時新加入的 chchch 不改變 needneedneed。
-
當窗口中滑出一位字符 chchch 時：
- 若 cnt[ch]>0cnt[ch]>0cnt[ch]>0，說明 chchch 未滑出窗口前我們對于字符 chchch 仍然還有需求（滑出去需求更大了），此時滑出去的 chchch 能夠使得 need+1need+1need+1；
- 若 cnt[ch]=0cnt[ch]=0cnt[ch]=0，說明 chchch 未滑出窗口前我們對于字符 chchch 剛好無需求（滑出去后會對字符 chchch 有需求了），此時滑出去的 chchch 能夠使得 need+1need+1need+1；
- 若 cnt[ch]<0cnt[ch]<0cnt[ch]<0，說明 chchch 未滑出窗口前我們對于字符 chchch 已無需求（過剩），此時滑出去的 chchch 不改變 needneedneed。
-
當 need=0need=0need=0 時，說明找到了一個滿足題意的窗口，使得中的字符能夠覆蓋 ttt。在記錄下答案的同時，我們還需要嘗試收縮窗口左邊界（參照上一步）。
具體實現(xiàn)可參照代碼和相關注釋：
代碼
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(t) > len(s):
return ''
cnt = collections.Counter(t) # 哈希表：記錄需要匹配到的各個元素的數(shù)目
need = len(t) # 記錄需要匹配到的字符總數(shù)【need=0表示匹配到了】
n = len(s)
start, end = 0, -1 # 記錄目標子串s[start, end]的起始和結(jié)尾
min_len = n + 1 # 符合題意的最短子串長度【初始化為一個不可能的較大值】
left = right = 0 # 滑動窗口的左右邊界
for right in range(n):
# 窗口右邊界右移一位
ch = s[right] # 窗口中新加入的字符
if ch in cnt: # 新加入的字符位于t中
if cnt[ch] > 0: # 對當前字符ch還有需求
need -= 1 # 此時新加入窗口中的ch對need有影響
cnt[ch] -= 1
# 窗口左邊界持續(xù)右移
while need == 0: # need=0，當前窗口完全覆蓋了t
if right - left + 1 < min_len: # 出現(xiàn)了更短的子串
min_len = right - left + 1
start, end = left, right
ch = s[left] # 窗口中要滑出的字符
if ch in cnt: # 剛滑出的字符位于t中
if cnt[ch] >= 0: # 對當前字符ch還有需求，或剛好無需求(其實此時只有=0的情況)
need += 1 # 此時滑出窗口的ch會對need有影響
cnt[ch] += 1
left += 1 # 窗口左邊界+1
return s[start: end+1]
變長滑動窗口：數(shù)組
題解：https:///problems/shortest-supersequence-lcci/solution/by-flix-difn/
題目回顧：
假設你有兩個數(shù)組，一個長一個短，短的元素均不相同。找到長數(shù)組中包含短數(shù)組所有的元素的最短子數(shù)組，其出現(xiàn)順序無關緊要。
返回最短子數(shù)組的左端點和右端點，如有多個滿足條件的子數(shù)組，返回左端點最小的一個。若不存在，返回空數(shù)組。
示例 1：
輸入:
big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
small = [1,5,9]
輸出: [7,10]
示例 2：
輸入:
big = [1,2,3]
small = [4]
輸出: []
提示:
big.length <= 100000
1 <= small.length <= 100000
解題思路：
本題與上述 76. 最小覆蓋子串 和 劍指 Offer II 017. 含有所有字符的最短字符串 幾乎一樣，盡管題目中說明了 smallsmallsmall 數(shù)組中的元素均不相同，但依然可以運用上述方法降維打擊。
將 bigbigbig 和 smallsmallsmall 分別類比為上述字符題目中的 sss 和 ttt 即可。
具體實現(xiàn)可參照代碼和相關注釋：
代碼
class Solution:
def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
if len(small) > len(big):
return []
cnt = collections.Counter(small) # 哈希表：記錄需要匹配到的各個元素的數(shù)目
need = len(small) # 記錄需要匹配到的元素總數(shù)【need=0表示匹配到了】
n = len(big)
res = [] # 記錄目標子數(shù)組的起始和結(jié)尾
min_len = n + 1 # 符合題意的最短字數(shù)組長度【初始化為一個不可能的較大值】
left = right = 0 # 滑動窗口的左右邊界
for right in range(n):
# 窗口右邊界右移一位
num = big[right] # 窗口中新加入的元素
if num in cnt: # 新加入的元素位于small中
if cnt[num] > 0: # 對當前元素num還有需求
need -= 1 # 此時新加入窗口中的元素num對need有影響
cnt[num] -= 1
# 窗口左邊界持續(xù)右移
while need == 0: # need=0，當前窗口完全覆蓋了small
if right - left + 1 < min_len: # 出現(xiàn)了更短的子數(shù)組
min_len = right - left + 1
res = [left, right]
num = big[left] # 窗口中要滑出的元素
if num in cnt: # 剛滑出的元素位于small中
if cnt[num] >= 0: # 對當前元素num還有需求，或剛好無需求(其實此時只有=0的情況)
need += 1 # 此時滑出窗口的元素num會對need有影響
cnt[num] += 1
left += 1 # 窗口左邊界+1
return res
定長滑動窗口：異位詞
題解：https:///problems/permutation-in-string/solution/by-flix-ix7f/
題解：https:///problems/MPnaiL/solution/by-flix-0h27/
題目回顧：
給你兩個字符串 s1 和 s2 ，寫一個函數(shù)來判斷 s2 是否包含 s1 的排列。如果是，返回 true ；否則，返回 false 。
換句話說，s1 的排列之一是 s2 的 子串 。
示例 1：
輸入:
輸入：s1 = "ab" s2 = "eidbaooo"
輸出：true
解釋：s2 包含 s1 的排列之一 ("ba").
示例 2：
輸入：s1= "ab" s2 = "eidboaoo"
輸出：false
提示:
1 <= s1.length, s2.length <= 10^4
s1 和 s2 僅包含小寫字母
解題思路：
本題與 76. 最小覆蓋子串 和 劍指 Offer II 017. 含有所有字符的最短字符串 是類似的，最大的不同在于本題要求滑動窗口是 固定長度 的。
例如，對于s1 = "ab"，我們要在s2 = "eidbaooo"中找到一個與s1同樣長度的子字符串 s'使得其中各元素的數(shù)目與s1保持一致（即 s' 與 s1 為「異位詞」）。
借用下面兩道題目中的表述: 「異位詞」指字母相同，但排列不同的字符串。
因此，在窗口滑動的過程中，我們維持一個長度為 len(s1)len(s1)len(s1) 的滑動窗口，當窗口中待匹配的字符數(shù)目為 000 我們就找到了一個滿足要求的子串。
在上述題解和代碼的基礎上，稍作調(diào)整即可。
具體實現(xiàn)可參照代碼和相關注釋：
代碼
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
m, n = len(s1), len(s2)
if m > n:
return False
cnt = collections.Counter(s1) # 哈希表：記錄需要匹配到的各個字符的數(shù)目
need = m # 記錄需要匹配到的字符總數(shù)【need=0表示匹配到了】
for right in range(n):
# 窗口右邊界
ch = s2[right] # 窗口中新加入的字符
if ch in cnt: # 新加入的字符ch位于s1中
if cnt[ch] > 0: # 此時新加入窗口中的字符ch對need有影響
need -= 1
cnt[ch] -= 1
# 窗口左邊界
left = right - m
if left >= 0:
ch = s2[left]
if ch in cnt: # 剛滑出的字符位于s1中
if cnt[ch] >= 0: # 此時滑出窗口的字符ch對need有影響
need += 1
cnt[ch] += 1
if need == 0: # 找到了一個滿足題意的窗口
return True
return False
定長滑動窗口：異位詞的位置
題解：https:///problems/find-all-anagrams-in-a-string/solution/by-flix-s37y/
題解：https:///problems/VabMRr/solution/by-flix-octm/
題目回顧：
給定兩個字符串 s 和 p，找到 s 中所有 p 的 異位詞 的子串，返回這些子串的起始索引。不考慮答案輸出的順序。
異位詞 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1：
輸入: s = "cbaebabacd", p = "abc"
輸出: [0,6]
解釋:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的異位詞。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的異位詞。
示例 2：
輸入: s = "abab", p = "ab"
輸出: [0,1,2]
解釋:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的異位詞。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的異位詞。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的異位詞。
提示:
1 <= s.length, p.length <= 3 * 10^4
s 和 p 僅包含小寫字母
解題思路：
本題則在上述兩題 567. 字符串的排列 和 劍指 Offer II 014. 字符串中的變位詞 的基礎上記錄下滿足要求的定長滑動窗口的左端點。
因此，在窗口滑動的過程中，我們維持一個長度為 len(p)len(p)len(p) 的滑動窗口，當窗口中待匹配的字符數(shù)目為 need=0need=0need=0 時我們就找到了一個滿足要求的子串，記錄下此時窗口的左端點即可。
在上述代碼的基礎上，增加窗口左邊界的記錄即可。
具體實現(xiàn)可參照代碼和相關注釋：
代碼
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, m = len(s), len(p)
if m > n:
return []
cnt = collections.Counter(p) # 哈希表：記錄需要匹配到的各個字符的數(shù)目
need = m # 記錄需要匹配到的字符總數(shù)【need=0表示匹配到了】
res = []
for right in range(n):
# 窗口右邊界
ch = s[right] # 窗口中新加入的字符
if ch in cnt: # 新加入的字符位于p中
if cnt[ch] > 0: # 此時新加入窗口中的字符對need有影響
need -= 1
cnt[ch] -= 1
# 窗口左邊界
left = right - m
if left >= 0:
ch = s[left]
if ch in cnt: # 剛滑出的字符位于p中
if cnt[ch] >= 0: # 此時滑出窗口的字符對need有影響
need += 1
cnt[ch] += 1
if need == 0: # 找到了一個滿足題意的窗口，其左端點為right-m+1
res.append(right - m +1)
return res
|
