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

问题陈述

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

示例

1
2
3
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

思路分析

回文问题一般都是从字符串的中间向两端扩散，构造回文串也是类似的。

我们定义一个二维的dp数组，dp[i][j]的定义如下：对字符串s[i..j]，最少需要进行dp[i][j]次插入才能变成回文串。

我们想求整个s的最少插入次数，根据这个定义，也就是想求dp[0][n-1]的大小（n为s的长度）。

同时，base case 也很容易想到，当i == j时dp[i][j] = 0，因为当i == j时s[i..j]就是一个字符，本身就是回文串，所以不需要进行任何插入操作。

状态转移方程

如果我们现在想计算dp[i][j]的值，而且假设我们已经计算出了子问题dp[i+1][j-1]的值了，你能不能想办法推出dp[i][j]的值呢？

img

既然已经算出dp[i+1][j-1]，即知道了s[i+1..j-1]成为回文串的最小插入次数，那么也就可以认为s[i+1..j-1]已经是一个回文串了，所以通过dp[i+1][j-1]推导dp[i][j]的关键就在于s[i]和s[j]这两个字符。

这个得分情况讨论，如果s[i] == s[j]的话，我们不需要进行任何插入，只要知道如何把s[i+1..j-1]变成回文串即可：

……

阅读原文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class MinInsert {
    public int minInsertion(String str){
        int n=str.length();
        int[][] dp=new int[n][n];
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(str.charAt(i)==str.charAt(j)){
                    dp[i][j]=dp[i+1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
                }
            }
        }
        return dp[0][n-1];
    }

    public static void main(String[] args) {
        String str="aabbaag";
        MinInsert minInsert=new MinInsert();
        System.out.println(minInsert.minInsertion(str));
    }
}