# Readable Python solution (slow, not KMP)

• ``````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
``````

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