Readable Python solution (slow, not KMP)


  • 0
    class Solution(object):
        def shortestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            
            Algorithm: Look for occurrences of the first character in reverse order and check for palindrome of that length.
            
            """
            # Handle edge cases
            if len(s) < 2:
                return s
                
            # Reverse the whole string only once
            r = s[::-1]
            
            # First character the algorithm will look for
            first_character = s[0]
            
            # Search for longest palindrome substring
            last_position = s.rfind(first_character)
            while last_position > 0:
                
                # Palindrome length
                palindrome_length = last_position + 1
                
                # Check for palindrome of palindrome_length characters
                if s[:palindrome_length] == r[-palindrome_length:]:
                    
                    # Found longest palindrome
                    # Extend it on the left side to cover the whole string
                    return r[:(len(s) - palindrome_length)] + s
                   
                # Find next candidate substring
                last_position = s.rfind(first_character, 1, last_position)
    
            # Worst case
            return r[:-1] + s
    

Log in to reply
 

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