Python Solution. TLE


  • 0
    D
    class Solution(object):
        def findAnagrams(self, s, p):
            refer_dict=[0]*26
            res =[]
            
            for char in p:
                refer_dict[ord(char)-ord('a')]+=1
            
            for i in range(len(s)-len(p)+1):
                sub = s[i:i+len(p)]
                if self.helper(sub,refer_dict):
                    res.append(i)
            return res
            
            
        def helper(self,sub,refer_dict):
            char_dict=[0]*26
            for char in sub:
                char_dict[ord(char)-ord('a')]+=1
            for i in range(26):
                if char_dict[i]!=refer_dict[i]:
                    return False
            return True
    

    I'm taking each substring of length p starting from index 0 of s and checking if it is anagram or not. It is a solution of O(n*26). I'm not sure why I'm getting a TLE.


  • 0

    That's not O(n*26). Think about what happens when p is half as long as s.


  • 0
    D

    Hey @StefanPochmann !

    Actually it's O ( n* max(26,len(p))). But in the problem statement it is given that

     the length of both strings s and p will not be larger than 20,100.
    

Log in to reply
 

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