[牛客竞赛] Applese 的回文串（字符串）

链接：
来源：牛客网

题目描述

输入描述:

仅一行，为一个由字母和数字组成的字符串 s。

输出描述:

如果在插入一个字符之后可以构成回文串，则输出"Yes", 否则输出"No"。

示例1

输入

applese

输出

No

示例2

输入

java

输出

Yes

备注:

|s| ≤ 10⁵

分析：

从左右两边同时开始扫描字符串，遇到左右字符不相同时，在左 / 右添加一个字符，相当于右 / 左删除一个字符。

所以遇到左右字符不相同时，删除右 / 左的一个字符（右指针-1 / 左指针+1），再确认是否为回文串即可

以下代码：

#include <bits/stdc++.h>
using namespace std;
string s;
bool solve(int l,int r,bool flag)    //flag记录是否之前删除过字符
{                                    //false为已有字符被删除，反之为 true
	while(l<=r)
	{
		if(s[l]==s[r])
		{
			l++;
			r--;
		}
		else if(flag==true)     //如果还没有字符被删过
			     //删除左边一个字符   或   删除右边一个字符
			return solve(l+1,r,false)||solve(l,r-1,false);
		else      
			return false;       //否则返回 false
	}
	return true;
}
int main()
{
	cin>>s;
	if(solve(0,s.length()-1,true))
		printf("Yes");
    else
    	printf("No");
	return 0;
}