Applese 的回文串 (判断一个字符串去掉任意一个字符后是否是回文串)

淩亂°似流年 2022-04-23 08:50 264阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/330/I][https_ac.nowcoder.com_acm_contest_330_I]  
来源：牛客网

自从 Applese 学会了字符串之后，精通各种字符串算法，比如……判断一个字符串是不是回文串。

这样的题目未免让它觉得太无聊，于是它想到了一个新的问题。  
  
如何判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串？

## 输入描述: ##

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

## 输出描述: ##

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

示例1

## 输入 ##

复制

applese

## 输出 ##

复制

示例2

## 输入 ##

复制

java

## 输出 ##

复制

Yes

## 备注: ##

|s|≤105

> 思路：既然任意添加一个字符能使得原字符串变成回文串，那么任意移除一个字符也可以。遍历字符串，找到第一个不匹配的地方，然后将那一段字符串分别去掉最前面的一个字符和最后面的一个，如果该取出来的字符串能构成回文串，就yes，否则no。
> 
> 比如：“1233421” ，取出“334” ，分别变成“33”和“34”，得到“33”是回文的，那么Yes。
> 
> 时间复杂度：O（n）

#include<iostream>
    #include<string>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    bool is_huiwen(string s)//判断是否为回文串 
    {
    	string ss = s;
    	reverse(s.begin(),s.end());
    	if (ss==s)
    	return true;
    	return false;
    }
    int main()
    {
    	int n,m,j,k,i,T;
    	string s;
    	while(cin>>s)
    	{
    		bool flag = false;
    		for (i=0;i<s.size();i++)
    		{
    			if (s[i]!=s[s.size()-i-1])
    			break;
    		}
    		if (i==s.size())//如果输入的字符串本身就是回文串 
    		flag = true;
    		else
    		{
    			if (is_huiwen(s.substr(i+1,s.size()-2*i-1)) || is_huiwen(s.substr(i,s.size()-2*i-1)))
    			flag = true;
    		}
    		flag == true?cout<<"Yes":cout<<"No";
    		cout<<endl;
    	}
    	
    	return 0;
     }

[https_ac.nowcoder.com_acm_contest_330_I]: https://ac.nowcoder.com/acm/contest/330/I