首页 > 试题广场 >

变回文串的最少插入次数

[编程题]变回文串的最少插入次数

给定一个字符串，你可以在其任何位置插入新字符，请你算出要把这个字符串变成回文字符串最少需要几次插入操作。

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

示例1

输入

"nowcoder"

可以插入至 "rednowcwonder"

示例2

"aaa"

算法知识视频讲解

夏花灿烂秋叶静美

发表于 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 展开全文

要双休的闭门羹烹饪师进入人才库

发表于 2023-09-12 12:03:05

区间动态规划：按照区间dp的步骤来确定状态：dp[i][j]表示从i-j的字串变成回文串的最少插入次数，所以，i-j的字串一定是回文串。划分阶段：区间长度决策选择：原问题与子问题之间的关系是若str[i] == str[j]，则dp[i][j] 展开全文

贪心线段树字符串双指针

难度：

1条回答 12收藏 2076浏览

查看代码

扫一扫，把题目装进口袋