## [LeetCode] Minimum Window Substring — python

2017年01月10日 编程语言 ⁄ 共 1186字 ⁄ 字号 评论关闭

```class Solution:
# @return a string
def minWindow(self, S, T):
if not T or not S or len(T)>len(S):
return ''
res=''
s1=0
wordS={}
wordT={}
for i in T:
for s2 in xrange(len(S)):
if not self.check(wordT,wordS):
break
if s2==len(S)-1:
return res
s2+=1
while s2<=len(S):
while s1<s2 and self.checkOne(wordT,wordS,S[s1])>0:
#contain all
# print s1,s2,S[s1],wordS
wordS[S[s1]]-=1
s1+=1
print s1,s2,wordS
if (not res) or len(S[s1:s2])<len(res):
res=S[s1:s2]

if s2>=len(S):
break
s2+=1

## TLE
# for s1 in xrange(len(S)):
#     while s2<len(S) and self.check(wordT,wordS):
#         s2+=1
#     if not self.check(wordT,wordS):#contain all
#         if (not res) or len(S[s1:s2+1])<len(res):
#             res=S[s1:s2+1]
#     s1+=1
#     wordS[S[s1-1]]-=1
return res

def check(self, dictT, dict2):
for key in dictT:
try:
if dictT[key]>dict2[key]:
return key
except Exception, e:
return key
return ''

def checkOne(self, dictT, dict2, key):
if key in dictT:
try:
return dict2[key]-dictT[key]
except Exception, e:
return -1
else:
return 1