My non-recursive Python solution


  • 1
    S

    The basic idea here is that I run through the sequence of characters and try to find the longest possible palindrome that starts at the beginning of the string. Once identified I take the remainder of the string reverse it and prefix it onto the original string.

    The identification of the longest possible palindrome (starting at the first character of the string) is identified by running through the sequence and summing up the difference and cubed difference between current character and the previous character. Upon encountering a complete palindrome both the sum of the difference and cubed difference should be zero. Such positions are stored in a list and are explored in reverse to identify the largest palindromic sub-sequence.

    class Solution:
        # @param {string} s
        # @return {string}
        def shortestPalindrome(self, s):
            zero_pos = []
            length = len(s)
            if length <= 1:
                return s
            elif self.is_palindrome(s):
                return s
            cur_sum = 0
            cur_sum_cubued = 0
            for i in xrange(1, length):
                diff = ord(s[i]) - ord(s[i-1])
                cur_sum += diff
                cur_sum_cubued += diff**3
                if cur_sum == 0 and cur_sum_cubued == 0:
                    zero_pos.append(i)
    
            max_palindrome_pos = 0
            for pos in reversed(zero_pos):
                #print pos
                if self.is_palindrome(s[:pos+1]):
                    max_palindrome_pos = pos
                    break
    
            prefix = s[max_palindrome_pos+1:]
            return prefix[::-1]+s
    
        def is_palindrome(self, s):
            length_s = len(s)
            i = 0
            while s[i] == s[length_s - 1 - i] and i < length_s/2:
                i += 1
            if i < (length_s/2):
                return False
            else:
                return True

Log in to reply
 

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