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

Minimum Window Substring

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

Description

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Solution

sliding Window

Code

  • submit code
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if(len(t) > len(s)):
            return  ""

        # create a need dict
        need_dict = {}
        for m in t:
            need_dict[m] = need_dict.get(m,0) + 1

        left = 0
        right = 0
        valid = 0
        win_dict = {}

        tmp_result = ""
        result = ""
        while left < len(s):
            input = s[left]
            left += 1

            # updat Window
            win_dict[input] = win_dict.get(input,0) + 1
            tmp_result += input


            if(need_dict.get(input)):
                if(need_dict.get(input) == win_dict.get(input)):
                    valid += 1

            #The time to decrease slide window?
            while valid == len(need_dict):
                if(len(tmp_result) < len(result) or result == ""):
                    result = tmp_result


                output = s[right]
                right += 1

                win_dict[output] = win_dict.get(output) - 1
                if(win_dict.get(output,0) < need_dict.get(output,0)):
                    valid -= 1
                tmp_result = tmp_result[1:] # Delete The First Character

        return result
  • Full Code
class Solution:
    def minWindow(self, s: str, t: str) -> str:


        if(len(t) > len(s)):
            return  ""

        # 构造需求字典
        need_dict = {}
        for m in t:
            need_dict[m] = need_dict.get(m,0) + 1

        left = 0
        right = 0
        valid = 0
        print(need_dict)
        win_dict = {}

        tmp_result = ""
        result = ""
        while left < len(s):
            input = s[left]
            left += 1

            # 窗口数据字典更新
            win_dict[input] = win_dict.get(input,0) + 1
            tmp_result += input # 窗口字符串
            # print("tmp_result",tmp_result)

            # 需求字典有效值判断
            if(need_dict.get(input)):
                if(need_dict.get(input) == win_dict.get(input)):
                    valid += 1
                    # print(win_dict)

            # 缩小的条件是啥?
            # 窗口中的字符串满足需要的基本数据,但不一定是最小的字符串
            while valid == len(need_dict):
                print("valid: " + str(valid) + "\tneed: " + str(need_dict))
                print("tmp_result " + str(tmp_result))
                # 更新result为长度最小的字符串
                # 及求取最优节
                if(len(tmp_result) < len(result) or result == ""):
                    result = tmp_result


                output = s[right]
                right += 1

                win_dict[output] = win_dict.get(output) - 1
                if(win_dict.get(output,0) < need_dict.get(output,0)):
                    valid -= 1
                tmp_result = tmp_result[1:] # 删除第一个字符
            print("\n#################################")
            print(tmp_result)



        return result



S = Solution()
s = "ADOBECODEBANC"
t = "ABC"
# s = "a"
# t = "a"
print("result",S.minWindow(s,t))



# print("******************")
# print(s[1:])


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

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


要不聊聊?

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

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码