214.最短回文串
题目：
给定一个字符串 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-1while j >=0:if s[i] == s[j]:i+= 1j-= 1if i == n:return s# s2翻转 + 还需要递归的部分（s1) + s2return 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]) + 1return dp[0][n-1]