题目
题目链接:
https://www.nowcoder.com/practice/bae2652b4db04a438368238498e4c13e
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/
思路
参考答案C++
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param str string字符串
* @return int整型
*/
int minInsert(string str) {
//动态规划,详细注释看Go答案
int n = str.size();
vector<vector<int>> dp(n, vector<int>(n ));
for (int i = 0; i < n - 1; i++) {
dp[i][i + 1] = str[i] == str[i + 1] ? 0 : 1;
}
for (int i = n - 3; i >= 0; i--) {
for (int j = i + 2; j < n; j++) {
int cur = dp[i][j - 1];
if (dp[i + 1][j] < cur) {
cur = dp[i + 1][j];
}
dp[i][j] = cur + 1;
if (str[i] == str[j]) {
cur = dp[i + 1][j - 1];
if (dp[i][j] > cur) {
dp[i][j] = cur;
}
}
}
}
return dp[0][n - 1];
}
};
参考答案Java
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param str string字符串
* @return int整型
*/
public int minInsert (String str) {
//https://blog.csdn.net/xiaolu567/article/details/125906480
//动态规划
int n = str.length();
int[][] dp = new int[n][n];
//填充倒数第二行开始的对角线:dp[i][i+1]
//第一条dp[i][i]对应的对角线不用填,因为都是0,即插入0次,因为是每个字符自己
for (int i = 0; i < n - 1 ; i++) {
dp[i][i + 1] = str.charAt(i) == str.charAt(i + 1) ? 0 : 1;
}
//从下往上,倒数第三条对角线开始填dp[i][i+2]
for (int i = n - 3; i >= 0 ; i--) {
for (int j = i + 2; j < n ; j++) {
//自己的左边left和下边bottom,取最小+1
dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
if (str.charAt(i) == str.charAt(j)) {
//如果相当,自己和左下方对比,取最小
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
}
}
}
return dp[0][n - 1];
}
}
参考答案Go
package main
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param str string字符串
* @return int整型
*/
func minInsert(str string) int {
//https://blog.csdn.net/xiaolu567/article/details/125906480
//动态规划
n := len(str)
dp := make([][]int, n)
//第一条对角线dp[i][i]不用填,都是0
//填充第二条对角线,dp[i]i+1]
dp[0] = make([]int, n)
for i := 0; i < n-1; i++ {
dp[i+1] = make([]int, n)
cur := 0
if str[i] != str[i+1] {
cur = 1 //i和i+1位置不相等,那么要插入一个后,i和i+1位置变成回文
}
dp[i][i+1] = cur
}
//第一条对角线,第二条对角线都处理了
//接下来从第三条对角线开始处理,从下往上处理
for i := n - 3; i >= 0; i-- {
for j := i + 2; j < n; j++ {
cur := dp[i][j-1]
if cur > dp[i+1][j] {
cur = dp[i+1][j]
}
dp[i][j] = cur + 1 //左边和下边选最小的+1
if str[i] == str[j] {
if dp[i+1][j-1] < dp[i][j] {
dp[i][j] = dp[i+1][j-1] //如果i位置和j位置相等,那么自己和左下角比较,谁小取谁
}
}
}
}
return dp[0][n-1]
}
参考答案PHP
<?php
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param str string字符串
* @return int整型
*/
function minInsert( $str )
{
//https://blog.csdn.net/xiaolu567/article/details/125906480
//动态规划
//详细注释看go答案
$n = strlen($str);
$dp =[];
for($i=0;$i<$n-1;$i++){
$dp[$i][$i+1] = $str[$i]==$str[$i+1]?0:1;
}
for($i=$n-3;$i>=0;$i--){
for($j=$i+2;$j<$n;$j++){
$cur =$dp[$i][$j-1];
if($cur > $dp[$i+1][$j]){
$cur = $dp[$i+1][$j];
}
$dp[$i][$j] = $cur+1;
if($str[$i]==$str[$j]){
$cur = $dp[$i+1][$j-1];
if($dp[$i][$j] > $cur){
$dp[$i][$j] = $cur;
}
}
}
}
if($dp[0][$n-1] ==null) return 0;
return $dp[0][$n-1];
}