Accepted Python solution using hashtable


  • 12
    X
    class Solution:
        # @return a string
        def minWindow(self, S, T):
            indices = {}
            for char in T:
                indices[char] = []
            miss = list(T)
            start = 0
            end = len(S)
            for i in range(len(S)):
                if S[i] in T:
                    if S[i] not in miss and indices[S[i]] != []:
                        indices[S[i]].pop(0)
                    elif S[i] in miss:
                        miss.remove(S[i])
                    indices[S[i]].append(i)
                if miss == []:
                    maximum = max([x[-1] for x in indices.values()])
                    minimum = min([x[0] for x in indices.values()])
                    if maximum-minimum+1 < end-start+1:
                        start = minimum
                        end = maximum
            if miss != []:
                return ""
            else:
                return S[start:end+1]
    

    Basically I kept a dictionary to record the index of each character of T. Each time I found a window, (when miss == []), I checked the length of this window by subtracting the maximum index and the minimum index of the characters. If this window is the smallest one so far, I record its beginning and ending index as "start" and "end."


  • 0
    C

    Good thoughts. I give your a vote up. Your time complex seems to be len(S)*len(T), but this problem is easily solvable by using a dict for T and miss.


  • 0
    M

    It uses more space but is easier to understand.


  • 1
    D

    You can use deque instead of list. Then use popleft(), which takes O(1) time instead of pop(0)


Log in to reply
 

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