A different O(n) approach - 9 lines


  • 0
    H

    This is a dynamic programming solution
    scan from left to right. At each step (say position i that where S[i] is in T)

    • we want to find shortest interval that ends in i and includes all
      letters in T
    • we can do this by scanning from right (i) to left but that takes O(n) time and makes algorithm O(n^2). in order to make this constant time we keep 2 data structures:

    rpos: a sorted list of positions where rightmost positions of characters of T in S are kept
    r: a dictionary mapping from a character to the position. values of r is same as rpos

       def minWindow(self, S, T):
         res, rpos, r, Tcount = "",[], collections.defaultdict(list), collections.Counter(T)
         for i,c in filter(lambda x: x[1] in T,enumerate(S)): #go only over chrs exist in T
             if len(r[c]) == Tcount[c]: #reached limit. so we need to remove
                 rpos.remove(r[c].pop(0))
             r[c].append(i) #add to dict
             rpos.append(i) #add to array
             if len(rpos) == len(T) and (res=="" or rpos[-1]-rpos[0]<len(res)):
                 res = S[rpos[0]:rpos[-1]+1] 
         return res

  • 0
    Q

    Too concise to understand for me. Anyone can explain it a bit more and even better write this approach in Java? I don't know Python.


  • 0
    C

    I think the OJ has no implementation of the templates for collections, or not?


  • 0
    H

    no, many packages including 'collections' are imported by OJ


  • 0

    This isn't O(n) but O(n2) for three reasons:

    • Every r[c].pop(0) is only O(n).
    • Every rpos.remove(...) is only O(n).
    • Every res = S[rpos[0]:rpos[-1]+1] is only O(n).

    I added cost counters:

    def minWindow(self, S, T):
        cost1 = cost2 = cost3 = 0
        res, rpos, r, Tcount = "",[], collections.defaultdict(list), collections.Counter(T)
        for i,c in filter(lambda x: x[1] in T,enumerate(S)): #go only over chrs exist in T
            if len(r[c]) == Tcount[c]: #reached limit. so we need to remove
                rpos.remove(r[c].pop(0))
                cost1 += len(r[c])
                cost2 += len(rpos)
            r[c].append(i) #add to dict
            rpos.append(i) #add to array
            if len(rpos) == len(T) and (res=="" or rpos[-1]-rpos[0]<len(res)):
                res = S[rpos[0]:rpos[-1]+1]
                cost3 += len(res)
        print cost1, cost2, cost3
        return res
    

    For example for input S = "A" * 201 and T = "A" * 101, the costs are 10000 10000 10201.


Log in to reply
 

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