Python solution using binary search


  • 1
    D

    Use binary search for the length of palindromic string
    use mid & mid2 because the length can be even or odd

    class Solution(object):
        
        def n_length_Pl(self, st, lth):
            for i in range(len(st) - lth + 1):
                sub_st = st[i:i+lth]
                if sub_st == sub_st[::-1]:
                    return sub_st
            return ""
                
            
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            l = len(s)
            
            max_pl = ""
            
            # use binary search
            first = 0
            last = l
            
            while first <= last:
                
                mid = (first + last) / 2
                
                mid2 = min(l, mid + 1)
                
                chk_pl1 = self.n_length_Pl(s, mid)
                chk_pl2 = self.n_length_Pl(s, mid2)
            
                
                if chk_pl1 == "" and chk_pl2 == "":
                    last = mid - 1
                elif chk_pl1 != "" and chk_pl2 == "":
                    max_pl = chk_pl1
                    first = mid2 + 1
                elif chk_pl2 != "":
                    max_pl = chk_pl2
                    first = mid2 + 1
                
            return max_pl 
    

  • 0
    F

    I came up with the same concept (binary search), glad I'm not the only one xD
    Pretty sure it's not linear, but it gets accepted, so should be below O(n³) -- and O(1) storage other than the answer itself.

    I think it's something like O(N² * log N) (probably wrong..)


Log in to reply
 

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