LeetCode 76 [Minimum Window Subs

原题

给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的子串。

说明在答案的子串中的字母在目标字符串中是否需要具有相同的顺序？
——不需要。

样例
给出source = "ADOBECODEBANC"，target = "ABC" 满足要求的解 "BANC"

解题思路

• 窗口类问题 - 最自然的方法双层for循环，时间复杂度O(n2)解决
• 考虑优化 - 即那些状态不需要重复扫描？以"ADOBECODEBANC"为例
• 第一：left = 0, right = 5时出现一个可以覆盖ABC的最小子串，则right = 6, 7, ...都不需要在考虑，因为只会长度只会增加，不会成为更优解。直接退出while循环
• 第二：上一步退出循环以后，从left = 1开始，right需要退回吗？答案是不需要，因为left=0到right=5之间的情况已经判断过了，不需要再判断left=1到right=5之间的情况。但是仍在需要判断left=1和right=5此时是否valid。
• 需要写一个valid函数去判读"xxxxxxxx"是否包含"ABC"，两个都用hashmap记录出现次数，然后比较。时间复杂度可以当作常数 - O(1)
• 最后总的时间复杂度是O(2n) => O(n)

完整代码

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if not s or not t or len(t) > len(s):
            return ""
        right, res = 0, []
        length = sys.maxint
        sourceHash, targetHash = {}, {}
        for char in t:
            if char not in targetHash:
                targetHash[char] = 1
            else:
                targetHash[char] += 1
                
        for left in range(len(s)):
            while not self.valid(sourceHash, targetHash) and right < len(s):
                if s[right] not in sourceHash:
                    sourceHash[s[right]] = 1
                else:
                    sourceHash[s[right]] += 1
                right += 1
            if self.valid(sourceHash, targetHash) and right - left< length:
                length = right - left
                res = [left, right]
            sourceHash[s[left]] -= 1
        
        return "" if not res else s[res[0]:res[1]]
        
    def valid(self, sourceHash, targetHash):
        for key, value in targetHash.items():
            if key not in sourceHash:
                return False
            elif key in sourceHash and targetHash[key] > sourceHash[key]:
                return False
        return True