Skip to content

Instantly share code, notes, and snippets.

@cashlo
Created August 7, 2018 19:26
Show Gist options
  • Save cashlo/7e3e4e19116f4b36221f1e338d9f80e3 to your computer and use it in GitHub Desktop.
Save cashlo/7e3e4e19116f4b36221f1e338d9f80e3 to your computer and use it in GitHub Desktop.
class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
def non_palindrome_index(s):
i = 0
while i < len(s) - i:
if s[i] != s[-i-1]:
return i
i += 1
return -1
if non_palindrome_index(s) == -1: return s
i = 1
while i < len(s):
index = non_palindrome_index(s[:-i])
# print i, s[:-i], index
if index == -1:
return s[-1:-i-1:-1] + s
i += max(index-1, 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment