给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1：
输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：
输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
示例 4：
输入：s = "g"
输出：0
示例 5：
输入：s = "no"
输出：1
提示：
1 <= s.length <= 500
s 中所有字符都是小写字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome
第一次尝试
class Solution {
public int minInsertions(String s){
String rs = new StringBuilder(s).reverse().toString();
int length = s.length();
int[][] times = new int[length+1][length+1];
//计算s和倒序的rs的最长公共子串的长度
for(int i=1;i<=length;i++) {
for(int j=1;j<=length;j++) {
if(s.charAt(i-1) == rs.charAt(j-1))
times[i][j] = times[i-1][j-1]+1;
else
times[i][j] = max(times[i-1][j],times[i][j-1]);
}
}
int result = length; //初始为最大值
//分界线是任意的两个元素之间，可以左边或者右边没有元素
for(int i=0;i<=length;i++){ //处理最终回文串长度为偶数的情况
int minInsert = length - 2*times[i][length-i];
result = min(result,minInsert);
}
//分界线是某一个元素，这个元素必须存在，这个元素的左边和右边构成对称
for(int i=1;i<=length;i++){ //处理最终回文串长度为奇数的情况
int minInsert = (length-1)-2*times[i-1][length-i];
result = min(result,minInsert);
}
return result;
}
int max(int a,int b) { return a > b ? a : b; }
int min(int a,int b) { return a > b ? b : a; }
}
第二次尝试：
class Solution {
public int minInsertions(String s){
String rs = new StringBuilder(s).reverse().toString();
int length = s.length();
int[][] times = new int[length+1][length+1];
//计算s和倒序的rs的最长公共子串的长度
for(int i=1;i<=length;i++) {
for(int j=1;j<=length-i;j++) {
if(s.charAt(i-1) == rs.charAt(j-1))
times[i][j] = times[i-1][j-1]+1;
else
times[i][j] = max(times[i-1][j],times[i][j-1]);
}
}
int result = length; //初始为最大值
//分界线是任意的两个元素之间，可以左边或者右边没有元素
for(int i=0;i<=length;i++){ //处理最终回文串长度为偶数的情况
int minInsert = length - 2*times[i][length-i];
result = min(result,minInsert);
}
//分界线是某一个元素，这个元素必须存在，这个元素的左边和右边构成对称
for(int i=1;i<=length;i++){ //处理最终回文串长度为奇数的情况
int minInsert = (length-1)-2*times[i-1][length-i];
result = min(result,minInsert);
}
return result;
}
int max(int a,int b) { return a > b ? a : b; }
int min(int a,int b) { return a > b ? b : a; }
}
第三次尝试：
class Solution {
public int minInsertions(String s){
int length = s.length();
int[][] times = new int[length+1][length+1];
//计算s和倒序的rs的最长公共子串的长度
for(int i=1;i<=length;i++) {
for(int j=1;j<=length-i;j++) {
if(s.charAt(i-1) == s.charAt(length-j))
times[i][j] = times[i-1][j-1]+1;
else
times[i][j] = max(times[i-1][j],times[i][j-1]);
}
}
int result = length; //初始为最大值
//分界线是任意的两个元素之间，可以左边或者右边没有元素
for(int i=0;i<=length;i++){ //处理最终回文串长度为偶数的情况
int minInsert = length - 2*times[i][length-i];
result = min(result,minInsert);
}
//分界线是某一个元素，这个元素必须存在，这个元素的左边和右边构成对称
for(int i=1;i<=length;i++){ //处理最终回文串长度为奇数的情况
int minInsert = (length-1)-2*times[i-1][length-i];
result = min(result,minInsert);
}
return result;
}
int max(int a,int b) { return a > b ? a : b; }
int min(int a,int b) { return a > b ? b : a; }
}
第四次尝试：
class Solution {
public int minInsertions(String s){
int length = s.length();
int[][] dp = new int[length+1][length+1];
for(int i=1;i<=length;i++){
for(int j=1;j<=length;j++){
if(s.charAt(i-1)==s.charAt(length-j)) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
int result = length - dp[length][length];
return result;
}
int max(int a,int b) { return a > b ? a : b; }
}
第五次尝试：这次和之前使用的方法不同，枚举回文串的长度
class Solution {
public int minInsertions(String s){
int length = s.length();
int[][] dp = new int[length][length];
//长度为1的时候一定是回文串，因此len从2开始枚举
for(int len = 2;len<=length;len++){
for(int i = 0;i+len<=length;i++){
int j = i + len - 1;
if(s.charAt(i) == s.charAt(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][length-1];
}
private int min(int a,int b){ return a>b ? b : a; }
}
试试滚动数组？
class Solution {
public int minInsertions(String s){
int length = s.length();
int[][] dp = new int[2][length+1];
int k = 1; //k^1表示上一次记录的数据
for(int i=1;i<=length;i++){
for(int j=1;j<=length;j++){
if(s.charAt(i-1)==s.charAt(length-j)) dp[k][j] = dp[k^1][j-1]+1;
else dp[k][j] = max(dp[k^1][j],dp[k][j-1]);
}
k^=1;
}
int result = length - dp[k^1][length];
return result;
}
int max(int a,int b) { return a > b ? a : b; }
}
然而效果并不是很明显！！！
有推荐方法的请指教一下（能超过90%的那种）
总结：
【方法1】：把字符串s分成s1和s2两部分，寻找s1和rev(s2)的最长公共串.
【方法2】：找到字符串s的最长回文串s'，然后|s|-|s'|就是剩下的不能组成回文串的字符数，那个添加同样数量的字符使得s成为回文串.
【方法3】：dp[i][j]记录长度为len的字符串通过添加字符构造成回文串需要添加id最少字符,这里len = j-i+1
