175 ms Python solution Does any know the time complexity


  • 1
    V

    175 ms Python solution Does any know the time complexity

    def longestPalindrome(self, s):
        n=len(s)
        if n <2:
            return s
        Q2 = set()
        Q3 = set()
        Length = 1
        longestP = s[0]
        for i in xrange(n-2):
            if s[i] == s[i+1]:
                Q2.add((i,i+1))                
            if s[i] == s[i+2]:
                Q3.add((i,i+2))
        if s[n-2] == s[n-1]:
            Q2.add((n-2,n-1))
        if Q3:
            Length = 3
            longestP = Q3.pop()
            Q3.add(longestP)
        if Length<3 and Q2 :
            Length = 2
            longestP = Q2.pop()
            Q2.add(longestP)
        while Q2 or Q3:
            if len(Q3)>=len(Q2):
                curr = Q3
                offset = 1
            else:
                curr = Q2
                offset = 0
            start, end = curr.pop()
            middle = (start+end)/2
            
            if (middle-(Length+offset)/2<0) or (middle+(Length+offset)/2+1-offset >n-1):
                #print "break"
                continue
            
            
            longer = True
            for i in reversed(range((end-start-offset+1)/2+offset,(Length+offset)/2+1)):
                
                if s[middle-i] != s[middle+i+1-offset]:
                    longer = False
                    break
            if not longer:
                continue
            
            while True:
                i+=1
                
                if middle-i<0 or middle+i+1-offset>=n-1:                    
                    break
                if s[middle-i] != s[middle+i+1-offset]:                    
                    break
            
            i-=1
            Length = 2*(i+1)-offset
            longestP = (middle-i, middle+i+1-offset)
            curr.add(longestP)
            
        start, end = longestP
        return s[start:end+1]

  • 3
    G
    1. This algorithm firstly traverses the string, which is O(n), adding all 2-item & 3-item palindrome sub-strings to the sets.
    2. There are O(n) number of small sub-strings and they will be examined at least one time.
    3. In the best cases the longest candidate is examined firstly. Finding longestP cost O(n/2). Then use O(n) time to exclude other sub-strings. So the examine process cost O(1.5*n)
    4. In the worst cases, Length grows steadily. There will be O(sqrt(2n)) new sub-strings to be added to the sets. So the examine process cost O(2 * sqrt(2n) + n)
    5. Thus, it's O(n)

Log in to reply
 

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