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"
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
         """
         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