[ccNOV14] Let us construct palindrome

2014-12-09
竞赛题解 / 模拟
CodeChef

描述 Description

Given a string s. Can you make it a palindrome by deleting exactly one character? Note that size of the string after deletion would be one less than it was before.

输入格式 InputFormat

First line of the input contains a single integer T denoting number of test cases.

For each test case, you are given a single line containing string s.

输出格式 OutputFormat

For each test case, print YES or NO depending on the answer of the problem.

样例输入 SampleInput

4
aaa
abc
abdbca
abba

样例输出 SampleOutput

YES
NO
YES
YES

CodeChef PRPALN

代码 Code

记录有多少位置是不匹配的即可。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=100005;
int i,j,t,n,m,l,r,k,z,y,x;
int f[maxn][2];
char a[maxn];
int T;
inline bool test1()
{
    int i,j,t;
    j=n-1;
    for (t=i=0;i<n && i<j;i++)
    {
        if (a[i]==a[j])
        {
            j--;
        }
        else
        {
            t++;
            if (t>1) return false;
        }
    }
    return true;
}
inline bool test2()
{
    int i,j,t;
    j=n-1;
    for (t=i=0;i<n && i<j;i++)
    {
        if (a[i]==a[j])
        {
            j--;
        }
        else
        {
            i--;
            j--;
            t++;
            if (t>1) return false;
        }
    }
    return true;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",a);
        n=strlen(a);
        if (test1() || test2()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}