76. Minimum Window Substring
這題用動態(tài)窗口一次性AC了，但是代碼寫的比較爛，有點虛，再去看看答案，看看別人怎么寫的

class Solution(object):
   def minWindow(self, s, t):
       """
       :type s: str
       :type t: str
       :rtype: str
       """
       h = {}
       for c in t:
           h[c] = h.get(c, 0) + 1
       
       start = 0
       end = 0
       window = ""
       length = sys.maxint
       i = 0
       while i < len(s):
           if s[i] in h:
               h[s[i]] -= 1
               if all([v <= 0 for v in h.values()]):
                   if end - start + 1 < length:
                       length = end - start + 1
                       window = s[start:end+1]
                   # move left side
                   while all([v <= 0 for v in h.values()]):
                       if s[start] in h:
                           h[s[start]] += 1
                       start += 1
                       if all([v <= 0 for v in h.values()]):
                           if end - start + 1 < length:
                               length = end - start + 1
                               window = s[start:end+1]
           i += 1
           end = i
           
       return window

找到一種記錄當前字符有效長度的解法，比我那種all()的解法簡直不知道好多少倍

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        
        if len(s) < len(t): 
            return ""
        
        collect = {}
        for item in t:
            if item in collect:
                collect[item] += 1
            else:
                collect[item] = 1
        # 記錄最大可能end和start而非記錄長度
        maxend = 2147483647        
        maxstart = 0
        start = end = 0
        count = len(t)
        
        while end < len(s):
            if s[end] in collect:
                # 移動右邊界，如果右邊屆正好是collect中缺少的部分，那么就減少count
                if collect[s[end]] > 0: 
                    count -= 1
                collect[s[end]] -= 1 # 注意此時collect中的值可能是負數(shù)
            end += 1
            
            while count == 0: # 說明找到一個可能性
                if end - start < maxend - maxstart:
                    maxend, maxstart = end, start
                # 移動左邊界
                if s[start] in collect:
                    collect[s[start]] += 1
                    if collect[s[start]] > 0:
                        count += 1
                start += 1
            
        if maxend - maxstart >= 2147483647:
            return ""
                
        return s[maxstart:maxend]