LeetCode 76. 最小覆盖子串 | Python

在这里时间复杂度为 O(n^2)，不太理想。

本篇幅使用的是滑动窗口的思想。这里使用双指针，通过一静一动来达到搜索的目的。大致的思路如下：

• 首先初始化双指针，同时指向字符串 S 的开始位置（假设定义 left、right），那么 [left, right) 这个区间就是我们说的窗口，我们通过指针移动来控制窗口的大小。（上面区间是左闭右开，这里在开始定义指针指向索引为 0 的位置时，因为右开，所以定义开始这部分就是空区间）
• 接下来，我们先移动 right 指针（left 指针静止不动），让它不断扩大窗口的大小，直到窗口包含字符串 T 中所有字符
• 这时，停止移动 right 指针，移动 left 指针。这个时候，窗口就会缩小，当窗口的字符串不符合包含字符串 T 中的所有字符时，这个时候，停止移动 left 指针。在这里，从停止移动 right 指针，进而移动 left 指针时，要记得更新结果（因为要找到最小的子串）
• 现在只要不断重复上面第 2 步和第 3 步，直到 right 指针到字符串 S 末尾时，那么程序结束。

具体的实现代码如下。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
 from collections import defaultdict
 
 win = defaultdict(int)
 t_dict = defaultdict(int)
 for i in t:
     t_dict[i] += 1
 
 # 定义指针
 left = 0
 right = 0
 # 初始化最小长度
 min_len = float('inf')

 # chr_count 用以表示滑动窗口包含字符数
 chr_count = 0
 # 最小子串起始位置
 begin = 0
 # s 长度
 s_len = len(s)
 # t 长度
 t_len = len(t)

 while right < s_len:
     # 移动窗口，
     if t_dict[s[right]] == 0:
  right += 1
  continue
     # 滑动窗口包含 T 字符数，当超过 T 其中字符个数时不在增加
     if win[s[right]] < t_dict[s[right]]:
  chr_count += 1

     win[s[right]]+=1
     right+=1

     # 当窗口包含 T 所有的字符时，缩小窗口
     while chr_count == t_len:
  # 这里更新子串的起始位置和长度
  if right-left < min_len:
      begin = left
      min_len = right - left
  # 缩小窗口
  if t_dict[s[left]] == 0:
      left += 1
      continue
  # 这里表示出窗时，窗口所包含 T 的字符刚好等于 T 中字符的个数
  # 这个时候再移动，窗口就不满足包含 T 所有字符的条件
  # 这里 chr_count - 1 ，循环结束
  if win[s[left]] == t_dict[s[left]]:
      chr_count -= 1

  win[s[left]]-=1
  left += 1

 return "" if min_len == float('inf') else s[begin:begin+min_len]