ABC#237 C

ABC#237 C C

原题链接
题目大意：给定一个字符串str，判断能否通过在该字符串头部添加’a’，使该字符串变成回文串。

基本思路：将str头部和尾部的’a’去除，看剩下的字符串是否为回文串。若剩下的子串不是回文串，则结论为否。
需要特别注意的是：由于只能在字符串头部添加’a’，因此若str头部的’a’的个数比尾部的’a’的个数多，则结论也是否。

技巧：回文串的判断

bool isPalindrome(string str)
{
    string str2 = str;
    reverse(str.begin(), str.end());

    if (str == str2) return true;
    else return false;
}

代码1：双指针

#include 
#include 
using namespace std;

const int N = 1000010;
char s[N];

int main()
{
    cin >> s;
    bool flag = 1;
    int i = 0, j = strlen(s) - 1, cnt1 = 0, cnt2 = 0;
    while (s[i] == 'a') i ++, cnt1 ++;
    while (s[j] == 'a') j --, cnt2 ++;
    
    if (cnt1 > cnt2) flag = 0;
    
    while (i < j)
    {
        if (i >= j) break;
        else if (s[i] != s[j]) 
        {
            flag = 0;
            break;
        }
        else i ++, j --;
    }
    
    if (flag) cout << "Yes";
    else cout << "No";
    return 0;
}

代码2：string

#include 
#include 
using namespace std;

#define all(x) (x).begin(), (x).end()

int main()
{
    string str, str2;
    int cnt1 = 0, cnt2 = 0;
    cin >> str;
    while (str.size() && str.back() == 'a') str.pop_back(), cnt1 ++; // 去掉尾部的‘a’
    reverse(all(str));
    while (str.size() && str.back() == 'a') str.pop_back(), cnt2 ++; //去掉头部的‘a’

    str2 = str;
    reverse(all(str));

    if (str == str2 && cnt2 <= cnt1) cout << "Yes";
    else cout << "No";
}