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
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Given a string S and a string T, find the minimum window ...
- 题目描述 Given a string S and a string T, find the minimum wi...
- 解题思路： 利用Array的index存两个string的词频。 什么情况下找到一个valid的字符； 什么情况下...
- 原题 给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的子...
