Python accepted queue solution, O(ST)


  • 0
    Y

    The idea is to keep a queue of existing matches, the element of the queue is a pair of 2 numbers, first one being the start index in S, and second being matched chars in T.

    For cases like S = 'ffffffffeeeeeaaa' and T = 'ffea', O(ST) is guaranteed by keep popping previous pairs if there are worse than later ones. Worse, meaning it has a earlier start(1st number in pair) and same match(2nd number in pair)

    class Solution:
        def minWindow(self, S, T):
            """
            :type S: str
            :type T: str
            :rtype: str
            """
            ret = ''
            exists = collections.deque()
            for i, c in enumerate(S):
                for exist in exists:
                    if T[exist[1]] == c:
                        exist[1] += 1
                if c == T[0]:
                    exists.append([i, 1])
                    
                    
                while len(exists) > 1 and exists[0][1] == exists[1][1]:
                    exists.popleft()
                if exists and exists[0][1] == len(T):
                    if not ret or i - exists[0][0] + 1 < len(ret):
                        ret = S[exists[0][0]:i+1]
                    exists.popleft()
                while exists and ret and i - exists[0][0] + 1 > len(ret):
                    exists.popleft()
    
            return ret
                            
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.