首页 > 代码库 > 最少插入字符分析

最少插入字符分析

2024-07-11 18:54:15   213人阅读

题目来源，待字闺中，原创@陈利人 ，欢迎大家继续关注微信公众账号“待字闺中”

原题给定字符串，可以通过插入字符，使其变为回文。求最少插入字符的数量。例如：

1. ab最少插入1个字符，变为*b*ab

2. aa最少插入0个字符

3. abcd最少插入3个字符，*dcb*abcd
分析：根据回文串的定义，很容易获得递归思路，首先比较第一个和最后一个字符，相等则插入个数等于中间的插入个数，不等，则可以通过在开头或最后添加一个字符，使得两头相等，比如abcd可以转化为abcda或dabcd，这样，递归方程为:当str[i]==str[j]时，fun(i,j)=fun(i+1,j-1);否则fun(i,j)=min(fun(i+1,j),fun(i,j-1))+1.容易看出，该递归具有重复子序列，加上题目要求最短，故有最优的含义，故可转化为动态规划，动态规划的转移方程一般和递归方程一样，只是求解时需要利用先前的结果。本题中，可以看出求解方向是从两头向内部，和回文串的判断一样，动态规划的思路是先求len=1，然后len=2,然后……，故可得如下代码：

int minInsertChar(char* src)
{
	if(src =http://www.mamicode.com/= NULL)return -1;>

本代码只代表个人观点，如有错误，请指正，谢谢


联系
我们