牛客寒假算法基础训练营4 I题(回文字符串)

c/c++

浏览数:235

2019-6-8

题意:题意很简单,就是让你判断是否可以通过插入一个字符使字符串成为回文串(若本身是回文串,则不需要操作)。

解题思路:最简单的思路就是先判断是不是回文串,如果是的话很显然我们可以直接再中间插入一个字符,输出“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.

一道很简单的基础题,之所以贴上是为了记录自己的刷题经历吧。

作者:回首不知身是客