LeetCode 1312. 让字符串成为回文串的最少插入次数

给你一个字符串 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; }
}

leetcode也是提供这样的方法，上面的方法使用了数组内存消耗较大，如图

试试滚动数组？

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