题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

• 注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

• 示例

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”

思路

滑动窗口算法/快慢指针算法，我这是卡在细节许久了，找到了如下的解决办法，也学到了一点新的知识点。具体可以参考https://emperinter.com/2022/01/26/20220126/

• 本地调试的完整代码

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        #Base Condition
        if not s or not t: return ""
        t_counter = Counter(t)
        left = right = 0
        # 滑动窗口里面的数据
        window_dict = {}
        result = []

        while right < len(s):
            # 把当前的字符加到滑动窗口里面并且判断是否满足条件
            # dict的默认方法：
            # dict.get(key, default=None)
            # 返回指定键的值，如果键不在字典中返回默认值 None 或者指定的默认值。
            window_dict[s[right]] = window_dict.get(s[right], 0) + 1

            if self.isFit(window_dict, t_counter):
                # 如果满足条件就开始移动left指针
                while left <= right:
                    print("right:" + str(right) + "\tleft:" + str(left))
                    # 把当前的字符从滑动窗口里面移出
                    window_dict[s[left]] -= 1
                    left += 1
                    # 因为话单窗口是左闭右开，所以是not，并以此为判断。
                    if not self.isFit(window_dict, t_counter):
                        # 结果列表是一个sd的字符串
                        result.append(s[left - 1:right + 1])
                        break
            right += 1

        print(result)
        return sorted(result, key=lambda i: len(i))[0] if result else ""

    # 判断滑动窗口里面的数据是否满足t的需求量
    def isFit(self, window_dict: dict, t_counter: Counter) -> bool:
        for each_t in t_counter:
            if t_counter[each_t] > window_dict.get(each_t, 0):
                return False
        return True

S = Solution()

minStr = S.minWindow("ADOBECODEBANCABCC","ABCCD")

print("#########################")
print(minStr)