最近在用python刷leetcode的题,发现写起来比c++快多了~
这道题应该是双指针s1,s2,从头扫描,每一步先移动s2,使s1-s2范围内包含答案,随后移动s1,使包含结果的字符串最短,
刚开始做的时候TLE了,因为check的时候把dict过了一遍,太慢了,后来改为移动s1的时候,只check删除的s1指向的字符是否还够。
代码如下:
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: self.addToDict(i,wordT) for s2 in xrange(len(S)): self.addToDict(S[s2],wordS) 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 self.addToDict(S[s2],wordS) s2+=1 ## TLE # for s1 in xrange(len(S)): # while s2<len(S) and self.check(wordT,wordS): # s2+=1 # self.addToDict(S[s2-1],wordS) # 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 def addToDict(self, item, dict): dict.setdefault(item,0) dict[item]+=1