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

问题陈述

给你一个字符串 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]的大小(ns的长度)。

同时,base case 也很容易想到,当i == jdp[i][j] = 0,因为当i == js[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));
}
}