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]
网友评论