Share a nlogn solution, but TLE in python; however, I think i would be fine if in C.


  • 0
    M
    def suffix_array(s): 
        return [s[i:] for i in xrange(len(s)-1)]
     
    def count_prefix(a, b): 
        if a[1] == b[1]: 
            return 0
            
        cnt = 0
        for i in range(min(len(a[0]), len(b[0]))): 
            if a[0][i] == b[0][i]: 
                cnt += 1
        return cnt 
        
    class Solution:
        # @return a string
        def longestPalindrome(self, s):
            n = len(s)
            S = s 
            R = s[::-1] 
            s_sfx = zip(suffix_array(S), [0] * n)
            r_sfx = zip(suffix_array(R), [1] * n) 
            
            lst = sorted(s_sfx + r_sfx, key=lambda t: t[0]) 
            
            m_len = 0
            m_str = ''
            for i in range(len(lst)-1): 
                l = count_prefix(lst[i], lst[i+1]) 
                if l > m_len: 
                    m_len = l 
                    m_str = lst[i][0][:m_len]
                
            return m_str
            
    if __name__ == '__main__': 
        print Solution().longestPalindrome(raw_input().strip())
    

    if n^2 solution can pass the test in C+/Java, I suggest to loose the time limit when code written in Python :-)


  • 0
    S

    Questions about code you've written must describe the specific problem clearly, elaborate thoughts based on code and preserve code formatting as well. Please read the FAQ for more info.


  • 0
    S

    The current version of the algorithm has a bug in it:

    def count_prefix(a, b): 
    if a[1] == b[1]: 
        return 0
    
    cnt = 0
    for i in range(min(len(a[0]), len(b[0]))): 
        if a[0][i] == b[0][i]: 
            cnt += 1
    return cnt 
    

    Should probably be like this:

    def count_prefix(a, b): 
    if a[1] == b[1]: 
        return 0
    
    cnt = 0
    for i in range(min(len(a[0]), len(b[0]))): 
        if a[0][i] == b[0][i]: 
            cnt += 1
        else:
            return cnt
    return cnt 
    

    This makes it work a bit better, but it still fails on the following input for me:

    abcxxkcba
    

    The output is "abc", but it should actually be "xx". "abc" is not a palindrome.

    Maybe I made a mistake somewhere.


Log in to reply
 

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