首页 > 试题广场 >

变回文串的最少插入次数

[编程题]变回文串的最少插入次数
  • 热度指数：515 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个字符串，你可以在其任何位置插入新字符，请你算出要把这个字符串变成回文字符串最少需要几次插入操作。

数据范围：字符串的长度满足 1 \le n \le 2000 \，字符串中仅包含小写的英文字母
示例1

输入

"nowcoder"

输出

5

说明

可以插入至 "rednowcwonder"
示例2

输入

"aaa"

输出

0

备注:

算法知识视频讲解
开通博客
头像 夏花灿烂秋叶静美
发表于 2022-04-26 10:57:52
动态规划 :初始化dp[i][i]=0， 从右下角开始比较i=n-2开始，第i个字符和其后的所有字符对比填充，若字符不相等，则dp[i][j]=min(dp[i][j-1],d[i+1][j])+1;若相等则dp[i][j]=d[i+1][j-1]。     n o w c 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 咸鱼2号跃龙门
发表于 2023-09-12 12:03:05
区间动态规划：按照区间dp的步骤来确定状态：dp[i][j]表示从i-j的字串变成回文串的最少插入次数，所以，i-j的字串一定是回文串。划分阶段：区间长度决策选择：原问题与子问题之间的关系是 若str[i] == str[j]，则dp[i][j] 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-11-12 12:19:37
import java.util.*; /** * NC376 变回文串的最少插入次数 * @author d3y1 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-09-30 13:19:03
import java.util.*; /** * NC376 变回文串的最少插入次数 * @author d3y1 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-06-13 16:35:08
import java.util.*; /** * NC376 变回文串的最少插入次数 * @author d3y1 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 线段树 字符串 双指针
难度：
2条回答 4815浏览

热门推荐

通过挑战的用户

查看代码

相关试题

变回文串的最少插入次数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号