怎么把非回文字符串添加最少的字符成为回文字符串

怎么把非回文字符串添加最少的字符成为回文字符串,第1张

最关键的是弄懂f中存的数据的含义

我觉得应该是

从原始的字符串的第j个位置

提取出i个字符形成的子串

需要添加f[i][j]个字符可以形成回文

按照这个思路

初始化

for(i

=

0

i

<

n

i++)

{

f[0][i]

=

0

f[1][i]

=

0

}

对于任意位置

提取出0或者1个字符

自然可以认为是回文

不需要添加字符

即添加0个字符

事实上

这个循环可以去掉

因为上面已经有

memset(f,

0,

sizeof(f))

然后对子串大小进行循环

这个是外循环

对每个大小的子串

进行提取位置的循环

这个是内循环

核心转移公式

if(s[j]

==

s[i+j-1])

{

f[i][j]

=

f[i-2][j+1]

}

else

if(f[i-1][j]

<

f[i-1][j+1])

{

f[i][j]

=

f[i-1][j]

+

1

}

else

f[i][j]

=

f[i-1][j+1]

+

1

对于从第j位提取长度为i的子串

如果这个子串的第一位s[j]和最后一位

s[i+j-1]相同

那么其需要添加的数量和去掉这两个字符后需添加数量相同

即f[i-2][j+1]

如果不同的话

那么由于i-1长度下最优方案已计算,这样要么在开头加结尾字符

要么在结尾加开头字符

转化为i-1长度的最佳方案递推

比较去头或者去尾的情况

选其较小者+1

即为当前最佳方案

最难理解的在于不等于这一步

多想一下f[i][j]的含义

如果还想不明白

再追问

我们继续讨论

PS:程序问题

不知道题目要求的最长可能输入是多少

但是从代码上看

可能是最长不超过1000个字符

这样对s[i+j-1]访问实际上是可能越界的

虽然不影响结果

因为相邻的是f

其开始部分一直为0

但并不是合格程序应有的

应该定义的空间为

s[2*max_len+1]

l[max_len+1][max_len+1]

program cs

const n=10000

var

s:array[1..n] of char

i,j:integer

c:string

begin

readln(c)

if (length(c) mod 2)<>0 then

begin

delete(c,(length(c) div 2)+1,1)

end

//删去奇数个字符中间字符。

i:=0j:=1

while j<=length(c) do

begin

if i=0 then

begin

inc(i)

s[i]:=c[j]

inc(j)

end//栈空,则直接压栈。

else

begin

if s[i]=c[j] then

begin

dec(i)

inc(j)

end//栈顶元素与当前字符相同,就出栈。

else

begin

inc(i)

s[i]:=c[j]

inc(j)

end//不同,就进栈。

end

end

if i=0 then writeln('True')

else writeln('False')//如果栈是空的,证明是回文。

end.

思路是对于奇数个字符,删去中间字符。

其余字符扫一个处理一个,s[]是栈,i是它的指针。

j是c的指针。


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/bake/11890358.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-19
下一篇 2023-05-19

发表评论

登录后才能评论

评论列表(0条)

保存