美文网首页
76. Minimum Window Substring

76. Minimum Window Substring

作者: 阿团相信梦想都能实现 | 来源:发表于2017-01-18 03:45 被阅读0次
    class Solution(object):
        def minWindow(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: str
            """
            #left, right pointers 
            # use dictionary as hash
            #positive and negative values represent in excess or in debt 
            l=len(s)
            min_len=float('inf')
            m_start=0
            hash_dict=collections.defaultdict(int)
            count=len(t) #count the number of char in t still unidentified in s 
            for ch in t: 
                hash_dict[ch]+=1
            left,right=0,0
            while right<l:
                if s[right] in hash_dict:
                    #when meet a key char, record in hash,(negative value represent in excess) 
                    #if it is one of what we are currently looking for(hash value>0), reduce count 
                    if hash_dict[s[right]]>0:count-=1
                    hash_dict[s[right]]-=1
                right+=1
                while count==0: 
                    if min_len>right-left+1:#record the shorter solution if encounter one 
                        m_start=left
                        min_len=right-left+1
                    if s[left] in hash_dict: 
                        #when we are to leave out one key char, register in hash
                        #only start looking for it on the right when hash value is positive 
                        hash_dict[s[left]]+=1
                        if hash_dict[s[left]]>0:count+=1 
                    left+=1 
            if min_len==float('inf'): return ''
            return s[m_start:m_start+min_len-1]
    

    相关文章

      网友评论

          本文标题:76. Minimum Window Substring

          本文链接:https://www.haomeiwen.com/subject/umuvbttx.html