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.