题意：题意很简单，就是让你判断是否可以通过插入一个字符使字符串成为回文串（若本身是回文串，则不需要操作）。
解题思路：最简单的思路就是先判断是不是回文串，如果是的话很显然我们可以直接再中间插入一个字符，输出“Yes”，如果不是回文串的话，只需要依次去掉一个字符，判断剩下的字符串是否为回文串，是的话就输出“Yes”，如果一直判断到最后都不是回文串，就输出“No”。
但很显然，这是一个复杂度为O(n^2)的方法，不适用于这一题。
这里给出一个O(n)的解法，那就是先找到不匹配的位置，然后提出中间不匹配的字符串，分别判断其去掉头和去掉尾是否为回文串，其中有一个是回文串就可以输出“Yes”了。
判断是否为回文的函数
1 bool hw(string str)
2 {
3 string s = str;
4 reverse(s.begin(), s.end());
5 return s == str;
6 }
主要代码
1 //立个flag
2 bool flag = false;
3 //保存遍历到字符串的位置
4 int i;
5 //开始寻找不匹配串，遍历一半就好
6 for( i = 0; i < (int)str.size() / 2; ++i)
7 {
8 if(str[i] != str[str.size() - 1 - i])
9 {
10 break;
11 }
12 }
13 //原串为回文串时，i会遍历到上限
14 if(i == (int)str.size() / 2)
15 {
16 flag = true;
17 }
18 //判断不匹配段是否是回文串
19 else
20 {
21 flag = (hw(str.substr(i + 1, str.size() - 2 * i - 1)) || hw(str.substr(i, str.size() - 2 * i - 1)));
22 }
下面附上AC代码
/*========================================*/
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
//priority_queue
#include<list>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<ctime>
#include<complex>//.real.imag
#define rep(i,a) for(int i=0;i<a;++i)
#define repd(i,a) for(int i=1;i<=a;++i)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define rbf(a) for(auto elem:a)
#define MAXI INT_MAX
#define MINI INT_MIN
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;
struct node
{
};
/*========================================*/
//start your show!
bool hw(string str)
{
string s = str;
reverse(s.begin(), s.end());
return s == str;
}
int main()
{
string str;
cin >> str;
bool flag = false;
int i;
for( i = 0; i < (int)str.size() / 2; ++i)
{
if(str[i] != str[str.size() - 1 - i])
{
break;
}
}
if(i == (int)str.size() / 2)
{
flag = true;
}
else
{
flag = (hw(str.substr(i + 1, str.size() - 2 * i - 1)) || hw(str.substr(i, str.size() - 2 * i - 1)));
}
if(flag)
{
cout << "Yes" << endl;
}
else
cout << "No" << endl;
return 0;
}
/*========================================*/
//thank for your use.
一道很简单的基础题，之所以贴上是为了记录自己的刷题经历吧。
原文地址：https://www.cnblogs.com/cloudplankroader/p/10339983.html
