Python solution with TLE problem


  • 0
    Y

    Hi, it's the first time for me to write codes on leetcode.
    The test result is right but the submission result isn't and the problem is Time Limit Exceeded.
    Could someone help me with this problem?
    Thanks!

    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            i=0
            result=[]
            if len(s)>=len(p):
                while(i<(len(s)-len(p)+1)):
                    flag=0
                    for ch in range(0,len(p)):
                        if p[ch] in s[i:i+len(p)]:
                            flag=1
                        else:
                            flag=0
                            break
                    if flag==1:
                        result.append(i)
                    i+=1
            return result
    

  • 0
    J

    Because you are reconstructing the sub-string every single time.


  • 0
    Y

    Thanks for your reply :) , but I'm stilled a little confused.
    Do you mean "s[ i : i + len(p) ]" ? What happens if I use it?
    Does the TLE problem mean that if the string is quite long, it would take too much time that unacceptable?


  • 1
    J

    @yuanyi.yang s[i:i+len(p)] takes O(n) time. every time i+=1, you are going to spend o(n) time to reconstrcut the sub-string s[i:i+len(p)]. so total run-time complecity is going to be O(n^2). Refer to my sliding window solution, which is a O(N) solution.


Log in to reply
 

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