Fast recursive solution in Python - beats 96% of submissions


  • 0
    G
    class Solution(object):
        def shortestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            # find prefix that can be a palindrome
            prefix_idx = 0 
            for i in range(len(s)-1, -1, -1):
                if s[i] == s[prefix_idx ]:
                    prefix_idx  += 1
    
            if prefix_idx == len(s): # the whole string is palindrome
                return s
    
            suffix = s[prefix_idx:] # this is definitely not palindromic
            return suffix[::-1] + self.shortestPalindrome(s[:prefix_idx]) + suffix

Log in to reply
 

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