Applese的回文串-dfs

链接：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[];

bool flag;

void dfs(int n,int m,int num)

{

    if(num>=) return;//错误数一旦超过2就返回，节省大量时间

    if(n>=m){ flag=true;return;}//只要有一个搜到最后，让全局变量flag为true再返回

    if(a[n]==a[m])

        dfs(n+,m-,num);

    else

    {

        dfs(n+,m,num+);

        dfs(n,m-,num+);

    }

}

int main()

{

    while(scanf("%s",a)!=EOF)

    {

        flag=false;

        int len=strlen(a);

        dfs(,len-,);

        if(flag)

            printf("Yes\n");

        else

            printf("No\n");

    }

    return ;

}