字符串，是否能添加一个字母将其变为回文串

关于这个问题，必须要具体问题具体分析。如果前提是：保证某个非回文字符串通过只要添加一个字母，肯定能够使它变为回慧指歼文串的话，那么从程序设计的角度上讲，就必然是可以通过编写程序代码的方式实现；但是如果前提是：并不能够保证：对非回文字符串只要添加一个字母，就肯定能够使该串变为回文串的话，那么你无论如何通过程序设计、编写代码的方式，也无法将其变为回文串。

现在的问题就是：并没有一个通用的数学定理能够证明、并保证该结论成立。所以才会有我前面所说的：需要具体问题具体分析。例如如下例子：

对于 ab 字符串，本身不是回文串（反过来是字符串：ba），但是通过在小写字母 b 的后面添加一个小写字母 a，可以使其成为回文串，即逗消：aba（正向、反向内容都相同）

但是对于 abcd 字符串，本身不是回文串（反过来是字符串：dcba），但是无论通过什么方法，都无法做到前冲只添加一个字母，使其成为一个回文串。

思路：两个指针，一个从左往右，一个从右往左，让瞎只能跳过坦拍空一次贺燃，第二次的时候及说明需要添加两个字符

#include "stdafx.h"

#include<iostream>

#include<string>

using namespace std

int main()

{

string str

while (cin>>str)

{

bool flag = true

bool move = true

int left = 0

int right = str.length() - 1

while (left<str.length() / 2 &&right>= str.length() / 2)

{

if (str[left] == str[right])

{

left++

right--

}

else if (right - 1 >= 0 &&str[left] == str[right - 1] &&move==true)

{

right--

move = false

}

else if (left + 1 >= 0 &&str[left+1] == str[right ] &&move == true)

{

left++

move = false

}

else

{

flag = false

break

}

}

if (flag == false)

{

cout <<"NO" <<endl

}

else

{

cout <<"YES" <<endl

}

}

return 0

}

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

我觉得应该是

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

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

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

按照这个思路

初始化

for(i = 0i <ni++)

{

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]

---