Why TLE? (in Python Solution)


  • 0
    E

    I have my solution below:

    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            d = {}
            for i in xrange(len(s)-len(p)+1):
        
                slst = list(s[i:i+len(p)])
                slst.sort()
                ssorted = "".join(slst)
        
                if ssorted not in d:
                    d[ssorted] = [i]
                else:
                    d[ssorted] += [i]
        
            plst = list(p)
            plst.sort()
            psorted = "".join(plst)
            return d[psorted] if psorted in d else []
    

    Isn't the time complexity O(n)? Why TLE???


  • 1
    D

    You are sorting the substring in each run. Which nlogn time. Hence it is not linear


Log in to reply
 

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