Friday, September 19, 2014

Leetcode: Minimum Window Substring @Python

class Solution:
    # @return a string
    def minWindow(self, S, T):
        count1={}; 
        for char in T:
            if char not in count1: count1[char]=1
            else: count1[char]+=1
        count=len(T)
        start=0; minSize=len(S)+1; minStart=0
        for end in range(len(S)):
            if S[end] in count1:
                count1[S[end]]-=1
                if count1[S[end]]>=0:
                    count-=1
            if count==0:
                while True:
                    if S[start] in count1:
                        if count1[S[start]]<0:
                            count1[S[start]]+=1
                        else:
                            break
                    start+=1
                if minSize>end-start+1:
                    minSize=end-start+1; minStart=start
        if minSize==len(S)+1: return ''
        else:
            return S[minStart:minStart+minSize]

No comments :

Post a Comment