接外包,有相关需求的可以联系我:Telegram | Email

LeetCode:76. 最小覆盖子串(hard)

该文章创建(更新)于01/28/2022,请注意文章的时效性!

题目

给你一个字符串 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)


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/01/28/minimum-window-substring/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码


阿里云国际版20美元
Vultr10美元
搬瓦工 | Bandwagon应该有折扣吧?
域名 | namesiloemperinter(1美元)