题目描述：
如何判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串？
输入描述：
仅一行，为一个由字母和数字组成的字符串 s。
输出描述：
如果在插入一个字符之后可以构成回文串，则输出"Yes", 否则输出"No"。
输入：applese
输出：No
解题思路：有三种思路；
① 寻找缺失字符，如果缺失字符小于等于1，那么就可以变成回文串
（偷来的代码如下）
②动态规划——
③补位:比如“abc”找到前后不一样的：试一下在后面补a→“abca”，判断是否是回文串，然后试在前面补c→“cabc”，再次判断。
（以下也是偷来的代码）
#include <stdio.h> #include <string.h> const int MAXN = 1e5; char str[MAXN + 5]; int judge(int l, int r) { while(l <= r && str[l] == str[r]) l++, r--; if(l > r) return true; return false; } int main() { scanf("%s", str + 1); //跳过0号位读入，方便补位 int len = strlen(str + 1); int l = 1, r = len; while(str[l] == str[r] && l <= r) l++, r--; if(l > r) { puts("Yes"); return 0; } str[l - 1] = str[r]; //左补 if(judge(l - 1, r)) { puts("Yes"); return 0; } str[r + 1] = str[l]; //右补 if(judge(l, r + 1)) { puts("Yes"); return 0; } puts("No"); return 0; }
ps：emmm，另外一种与补位相同的思路：删除，先判断是否是回文串，是的话就是Yes，比如 “sls”就可以插入依旧是一个回文串“slls”。如果不是回文串的话，那么就从前后同时找不同的那个字母，删去，判断是否形成回文串，即可。
#include <iostream> #include <string> #include <algorithm> using namespace std; bool IsHuiWen(string str) //注意标明类型 { for(int i = 0; i<(int)str.size()/2;i++){ if(str[i] != str[str.size()-1-i]) return false; } return true; } int main() { string str; cin>>str; bool flag = false; int i; for(i = 0; i<(int)str.size()/2;i++) //强行转换类型，str.size求长度 { if(str[i] != str[str.size()-1-i]) break;; } if(i == (int)str.size()/2) flag = true; else flag = (IsHuiWen(str.substr(i+1,str.size()-2*i-1)) || IsHuiWen(str.substr(i,str.size()-2*i-1))); //substr函数：第一位是开始复制的起始位置，第二位是复制的长度。 cout<< ((flag==true) ? "YES" : "NO")<<endl; return 0; }
