回文串（增减版）

题目描述：
如何判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串？
输入描述：
仅一行，为一个由字母和数字组成的字符串 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;
 }