给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

注意 ： 要求在字符串前面加入一个字符串，使得新字符串是回文，且长度是最短的。题目也可以改成从尾部加入

其实目的就是在s中找到一个以头部字符为起点的最长回文串s1，然后s2（s中不是s1的部分）翻转贴到s的前面就完事了。 但是复杂度是O(n**2)， 有一种马拉车算法能到O(N)。 这里不介绍。

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        i,j = 0, n-1
        while j >=0:
            if s[i] == s[j]:
                i+= 1
            j-= 1
        if i == n:
            return s
        # s2翻转 + 还需要递归的部分（s1) + s2
        return s[i:][::-1] + self.shortestPalindrome(s[:i]) + s[i:]
我的解法并没有按照寻找以0为起点的最长回文串来做 实际上都是正确的做法。
 
1312.让字符串成为回文串的最少插入次数
 
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
 请你返回让 s 成为回文串的 最少操作次数 。
 
注意，该题目可以允许在任意位置插入。
 
解法：动态规划。
 设dp[i][j]为让s[i:j+1]为回文串的最小插入次数。
 则转移方程为：
 当s[i] == s[j]: dp[i][j] = dp[i+1][j-1]
 当s[i] != s[j] , dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
 
class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n-2, -1, -1):
            for j in range(i+1, n):
                if s[i]== s[j]:
                    dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
        return dp[0][n-1]