Problem: 76. 最小覆盖子串
思路
滑动窗口,与之类似的有
209. 长度最小的子数组
解题方法
- 使用cnt_s和cnt_t分别记录s的子串的字母个数和t的字母个数,因为这里都是字母,所以可以用长度为52的数组记录,我这里采用哈希表,python中的字典
- l和r两个指针分别指向数组的左端,不断移动r来扩大窗口,并更新cnt_s
- 当cnt_s覆盖cnt_t的时候,通过移动l缩小窗口,并更新cnt_s
注:这里用Counter()的比较大小来判断cnt_s是否覆盖cnt_t
复杂度
时间复杂度: O ( Σ m + n ) O(Σm+n) O(Σm+n) 每个元素最多被遍历两次 O ( m ) O(m) O(m),每次比较是 O ( Σ ) O(Σ) O(Σ),这里 Σ Σ Σ代表字符串s元素的种类(本题最多为52)
空间复杂度: O ( n ) O(n) O(n) 哈希表记录个数
Code
class Solution:
def minWindow(self, s: str, t: str) -> str:
cnt_t = Counter(t) # 记录t的元素个数
cnt_s = Counter() # 记录s的子串的元素个数
n = len(s)
ans_l, ans_r = -1, n + 1
l, r = 0, 0
while r < n:
cnt_s[s[r]] += 1
# 判断s的子串是否满足
while cnt_s >= cnt_t:
if r - l < ans_r - ans_l:
ans_l, ans_r = l, r
cnt_s[s[l]] -= 1 # 左端点字母移出子串
l += 1
r += 1
return "" if ans_l < 0 else s[ans_l: ans_r+1]
优化
上述代码判断s的子串是否覆盖t,需要O(Σ)的时间复杂度,可以优化成O(1)
思路:用less代表s的子串没有覆盖t的字母的种类,扩大窗口(通过移动r)减小res,当less为0的时候,便可以移动l缩小窗口。在缩小窗口的时候需要判断窗口的左端点是否是t中的元素,如果是的话less需要加1
class Solution:
def minWindow(self, s: str, t: str) -> str:
ans_l, ans_r = -1, len(s) + 1 # 答案
l, r = 0, 0 # 窗口的左右指针
cnt_s = Counter() # 记录s子串的元素个数
cnt_t = Counter(t) # 记录t的元素的个数
less = len(cnt_t) # 代表s子串中没有覆盖t中元素的种类数(注:因为同一种元素可能有多个,所以是种类数不是数量)
while r < len(s):
cnt_s[s[r]] += 1
if cnt_s[s[r]] == cnt_t[s[r]]:
less -= 1
while less == 0:
if r - l < ans_r - ans_l:
ans_l, ans_r = l, r
# 窗口的左端点恰好是t中元素
if cnt_s[s[l]] == cnt_t[s[l]]:
less += 1
cnt_s[s[l]] -= 1
l += 1 # 移动左窗口
r += 1
return '' if ans_l < 0 else s[ans_l: ans_r+1]