题目

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
说明：

  • 如果 S 中不存这样的子串，则返回空字符串 ""。
  • 如果 S 中存在这样的子串，我们保证它是唯一的答案。

    方案一（collections.Counter）

  1. class Solution:
  2.     def minWindow(self, s: str, t: str) -> str:
  3.         if len(t) > len(s):
  4.             return ""
  6.         t_counter = collections.Counter(t)
  7.         i_j_counter = collections.Counter()
  9.         res = ""
  10.         # 双指针
  11.         i, j = 0, 0
  12.         while j < len(s):
  13.             i_j_counter += collections.Counter(s[j])
  14.             j += 1
  15.             while not t_counter - i_j_counter:
  16.                 if j - i == len(t): # s中包含子串 t
  17.                     return s[i:j]
  18.                 if not res or j - i < len(res):
  19.                     res = s[i:j]
  20.                 i_j_counter -= collections.Counter(s[i])
  21.                 i += 1
  23.         return res
  • 关键部分在于如何快速比较一个字符串是另一个字符串的子串；
  • 需要在遍历字符串的同时保存 window 内的字符串，同时高效判断该 window 内字符串是否包含字符串 t 中的所有字符；
  • 此处使用 python 内置的 collections.Counter

    方案二（leetcode）

from collections import defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        mem = defaultdict(int)
        for char in t:
            mem[char] += 1
        t_len = len(t)
        left = 0
        minLeft = 0
        minRight = len(s)

        for right, char in enumerate(s):
            if mem[char] > 0:
                t_len -= 1

            mem[char] -= 1
            if t_len == 0:
                while mem[s[left]] < 0:
                    mem[s[left]] += 1
                    left += 1
                if right-left < minRight-minLeft:
                    minLeft, minRight = left, right
                mem[s[left]] += 1
                t_len += 1
                left += 1
        return '' if minRight==len(s) else s[minLeft:minRight+1]