My code's complexity seems linear, just move two pointers, why always exceed time limit in the len(s)=100000 case?


  • 0
    J
    import sys
    class Solution(object):
        def minWindow(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: str
            """
            if len(s) == 0 or len(t) == 0 or len(t) > len(s):
                return ""
            start = 0
            end = 0
            current_start = 0
            current_end = 0
            current_length = sys.maxint
            get = {letter:0 for letter in set(t)}
            want = {letter:t.count(letter) for letter in set(t)}
            left = set(t)
            # print len(s),len(t)
            i = 0
            while end < len(s):
                # print i,end
                # print start,end,current_start, current_end
                # print len(left)
                while end < len(s):
                    if s[end] in set(t):
                        get[s[end]] += 1
                        if get[s[end]] >= want[s[end]] and s[end] in left:
                            left.remove(s[end])
                        if len(left) == 0:
                            end += 1
                            break
                    end += 1
                if end == len(s) and len(left)!=0:
                    break
                while start < end:
                    # print s[start],start
                    if s[start] in set(t):
                        get[s[start]] -= 1
                        if get[s[start]]<want[s[start]]:
                            left.add(s[start])
                            start += 1
                            break
                    start += 1
                if end-start < current_length:
                    current_length = end - start + 1
                    current_start = start -1
                    current_end = end
                
            return s[current_start:current_end]

  • 0
    T

    Are you sure it's solely n=len(s) that's the problem?

    For example bulding want from k=len(t) is an k^2 operation.

    Also there are many set(t)s in your code, maybe you need to create it once, not every iteration. Your main loop runtime just because set(t)s is: 2*n*k.

    Also how long does in set(t) take (not counting construction of set(t))? Make sure that all add/remove/in/[] operations are O(1).


Log in to reply
 

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