该文章创建(更新)于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.

• https://leetcode.com/problems/minimum-window-substring/

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:])

要不赞赏一下?

微信

支付宝

PayPal

Bitcoin