【文件属性】:
文件名称:构成回文序列最少要增加多少字符
文件大小:3KB
文件格式:JAVA
更新时间:2017-01-06 16:17:25
回文序列 增加字符数 构成回文序列 回文
构成回文序列最少要增加多少字符
方法一:
为递归比较数组的头和尾:
如果头尾对应相同,则回文序列求解递归求解去头尾的回文序列(X...X => ...);
如果头尾对应不同,则有两种情况,
一种是在尾部后面添加头(X...Y => X...YX => ...Y),
一种是在头部前面添加尾(X...Y => YX...Y => X...),
解法为递归求解两种情况,取情况小的那种。
方法二:
解法二为求出字符串与逆序字符串的最长公共子串,
需要增加数目为字符串总数减去最长公共子串长度。
http://blog.csdn.net/ssuchange/article/details/17385039