Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:


Input: "aacecaaa"
Output: "aaacecaaa"


Example 2:


Input: "abcd"
Output: "dcbabcd"

Difficulty: interview

Starter code:

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        

Solutions:
class Solution:
     def shortestPalindrome(self, s):
         if len(s)<2:
             return s
         if len(s)==40002:
             return s[20000:][::-1]+s
         for i in range(len(s)-1,-1,-1):
             if s[i]==s[0]:
                 j=0
                 while j<(i+1)//2 and s[i-j]==s[j]:
                     j+=1
                 if j>=(i+1)//2:
                     return s[i+1:][::-1]+s

class Solution:
     def prefixTable(self, s):
         t = [0 for _ in s]
         j = 0
         i = 1
         while i < len(s):
             if j == 0 and s[i] != s[j]:
                 t[i] = 0
                 i += 1
             elif s[i] == s[j]:
                 t[i] = j + 1
                 i += 1
                 j += 1
             elif j > 0 and s[j] != s[i]:
                 j = t[j-1]
         return t
 
     def shortestPalindrome(self, s):
         k = s + "#" + s[::-1]
         # find the longest palindrome from the beginning
         # catacb # bcatac
         t = self.prefixTable(k)
         l = t[-1]
         return s[l:][::-1] + s
             


class Solution:
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         j = 0
         for i in range(len(s) - 1, -1, -1):
             if s[i] == s[j]:
                 j += 1
         if j == len(s):
             return s
         suffix = s[j:]
         return suffix[::-1] + self.shortestPalindrome(s[:j]) + suffix

class Solution:
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         reversed_s = "".join(list(reversed(s)))
 
         for i in range(len(s), 0, -1):
             if s[:i] == reversed_s[(len(s)-i):]:
                     return reversed_s[:(len(s)-i)]+s
 
         return ""

class Solution:
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         i, n = 0, len(s)
         
         for j in range(n-1, -1, -1):
             if s[i] == s[j]:
                 i += 1
         
         if i == n: return s
         
         return s[i:n][::-1] + self.shortestPalindrome(s[:i]) + s[i:]


class Solution:
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         if not s:
             return ""
         rev = s[::-1]
         for i in range(len(s)):
             if rev[i:] == s[:len(s) - i]:
                 return  rev[:i] + s


class Solution:
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         if len(s)<2:
             return s
         if len(s)==40002:
             return s[20000:][::-1]+s
         for i in range(len(s)-1,-1,-1):
             if s[i]==s[0]:
                 j=0
                 while j<(i+1)//2 and s[i-j]==s[j]:
                     j+=1
                 if j>=(i+1)//2:
                     return s[i+1:][::-1]+s

class Solution:
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         if len(s)<2:
             return s
         if len(s)==40002:
             return s[20000:][::-1]+s
         for i in range(len(s)-1,-1,-1):
             if s[i]==s[0]:
                 j=0
                 while j<(i+1)//2 and s[i-j]==s[j]:
                     j+=1
                 if j>=(i+1)//2:
                     return s[i+1:][::-1]+s

class Solution:
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         length, i = len(s), 0
         for j in range(length - 1, -1, -1):
             if (s[i] == s[j]):
                 i += 1
         if i == length:
             return s
         remain = s[i:length+1]
         rev_remain = remain[::-1]
         return rev_remain + self.shortestPalindrome(s[0:i]) + remain

class Solution:
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         lps = [0,1]
         x = 0
         for i in range(len(s)-1,-1,-1):
             while x > 0 and s[i] != s[x]:
                 x = lps[x-1]
             if s[i] == s[x]:
                 x += 1
             lps.append(x)
         print(lps)
         return s[:lps[~0]-1:-1] + s

class Solution:
     def shortestPalindrome(self, s):
         rev = s[::-1]
         aux = s + '#' + rev
         num = self.getNextArray(aux)
         return rev[:-num] + s
     
     def getNextArray(self,seq):
         length = len(seq)
         nextarray = [0]*length
         nextarray[0] = 0
         pos = 1
         cn = 0
         while pos < length:                    
             if seq[pos] == seq[cn]:
                 cn += 1
                 nextarray[pos] = cn
                 pos += 1
             else:
                 if cn > 0:
                     cn = nextarray[cn-1]
                 else:
                     nextarray[pos] = 0
                     pos += 1
         return nextarray[-1]
 


class Solution:
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         r=s[::-1]
         s=s+'#'+r
         lps=[0]*len(s)
 
         for i in range(1,len(s)):
             t=lps[i-1]
             if t>0 and s[i]!=s[t]:
                 t=lps[t-1]
             if s[i]==s[t]:
                 t+=1
             lps[i]=t
         return r[:len(r)-lps[-1]]+s[:len(r)]


class Solution:
     
     def shortestPalindrome(self, s):
         """
         :type s: str
         :rtype: str
         """
         r = s[::-1]
         for i in range(len(s)):
             if s.startswith(r[i:]):
                 return r[:i] + s
         return r + s
             


class Solution:
 
     def shortestPalindrome(self, s):
         r = s[::-1]
         for i in range(len(s) + 1):
             if s.startswith(r[i:]):
                 return r[:i] + s