链接：https://ac.nowcoder.com/acm/contest/330/I
来源：牛客网
题目描述
自从 Applese 学会了字符串之后，精通各种字符串算法，比如……判断一个字符串是不是回文串。
这样的题目未免让它觉得太无聊，于是它想到了一个新的问题。
如何判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串？
输入描述:
仅一行，为一个由字母和数字组成的字符串 s。
输出描述:
如果在插入一个字符之后可以构成回文串，则输出"Yes", 否则输出"No"。
示例1
输入
applese
输出
No
示例2
输入
java
输出
Yes
备注:
|s|≤105
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<math.h> #include<set> #define ll long long #define inf 0x3f3f3f3f using namespace std; char a[100086]; bool flag; void dfs(int n,int m,int num) { if(num>=2) return;//错误数一旦超过2就返回，节省大量时间 if(n>=m){ flag=true;return;}//只要有一个搜到最后，让全局变量flag为true再返回 if(a[n]==a[m]) dfs(n+1,m-1,num); else { dfs(n+1,m,num+1); dfs(n,m-1,num+1); } } int main() { while(scanf("%s",a)!=EOF) { flag=false; int len=strlen(a); dfs(0,len-1,0); if(flag) printf("Yes\n"); else printf("No\n"); } return 0; }