Palindromic string

1312. Minimum Insertion Steps to Make a String Palindrome

# 双指针，一头一尾。如果left和right所指字符相同，那么left+1,right-1
# 如果不同，则表示需要插入字符了。有两种可能的插入方法：
# 在left-1处插入right所指向的字符，插入后，需要向左移动right指针，
# 在right+1处插入left所指向的字符，插入后，需要向右移动left指针

# dp[i][j]表示使区间[i,j]成为回文的最小插入次数
# s[i]==s[j],dp[i][j]=dp[i+1][j-1]
# s[i]==s[j],dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1

 1 class Solution(object):
 2     def minInsertions(self, s):
 3         """
 4         :type s: str
 5         :rtype: int
 6         """
 7 
 8 
 9         n=len(s)
10         if(n==1):return 0
11 
12         dp=[[0 for j in range(n)] for i in range(n)]
13         
14         for j in range(1,n):
15             for i in range(j-1,-1,-1):
16                 if(s[i]==s[j]):
17                     dp[i][j]=dp[i+1][j-1]
18                 else:
19                     dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1
20         
21         return dp[0][n-1]

1216. Valid Palindrome III

给出一个字符串 s 和一个整数 k，请你帮忙判断这个字符串是不是一个「K 回文」。

所谓「K 回文」：如果可以通过从字符串中删去最多 k 个字符将其转换为回文，那么这个字符串就是一个「K 回文」。