只删除一个元素来创建一个字符串回文。

I will be given string. I can remove only 1 element from it. After removing it if the new string becomes palindrome I have to print "Yes" otherwise "No".

我将得到字符串。我只能从其中移除一个元素。删除后，如果新字符串变成回文，我必须打印“是”否则“不”。

For example, I am given a string "abdbca". Here I can remove 5th index 'c' and make it palindrome and i have to print "Yes". On the other hand if the string is something like "abcd" I can not make it palindrome by removing only one character. Hence I have to print "No".

例如，我有一个字符串“abdbca”。在这里，我可以移除第五个索引'c'并使其回文，我必须打印"Yes"。另一方面，如果字符串像“abcd”一样，我不能只删除一个字符来使它成为回文。因此，我必须打印“不”。

I tried to do it but my code is not efficient enough. Can anybody please suggest me a efficient way to do it? I have to check strings of 10^5 length in less than 2.5 seconds.

我试着去做，但是我的代码不够有效。有人能告诉我一种有效的方法吗?我必须检查10 ^ 5的字符串长度小于2.5秒。

the way I tried to do it is shown bellow :

我试图这样做的方式是:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

#define REP(i,n)    for(int i=0;i<n;i++)
#define MAX 100010

using namespace std;

bool isPalindrome(char abc[]){
    int len = strlen(abc), lem = len/2;
    for(int i=0,n=len-1;i<=lem;i++,n--) if(abc[i]!=abc[n]) return false;
    return true;
}

int main()
{
    int tc;
    char str[MAX];
    scanf("%d",&tc);
    while(tc--){
        scanf("%s", str);
        int length = strlen(str), len = length - 1, z = length % 2, res = 0, ans = 0,         b=0,lem = length / 2;
        for(int i = 0;i<length;i++){
            int n=0, m=1;
            for(int x = 0, y = len;x<i && y!=i;x++,y--){
                n++;
                if(str[x]!=str[y]){
                    m=0; ++res;
                    break;
                }
            }
            if(i>lem) for(int x=n,y=len-n-1;x<y;x++,y--){
                if(str[x]!=str[y]){
                    m=0; ++res;
                    break;
                }
            }
            else for(int x=n+1,y=len-n;x<y;x++,y--){
                if(str[x]!=str[y]){
                    m=0; ++res;
                    break;
                }
            }
            if(m==1) {printf("YES\n");b++;break;}
        }
        //if(length <= res) printf("NO\n");
        if(b==0) printf("NO\n");
    }
    return 0;
}

3 个解决方案

#1

Since you you only need to remove one character, you can do so in linear time by modifying palindrome checking. The idea is that you compare characters from the beginning to characters from the end and stop at the first mismatch. If you remove one character from the mismatching pair and get a palindrome, then return true, otherwise return false. I implemented the idea in C++ below.

由于您只需要删除一个字符，您可以在线性时间内通过修改回文检查来实现。其思想是，您将字符从开头到字符进行比较，并在第一次不匹配时停止。如果您从错误匹配项中删除一个字符，并得到一个回文，那么返回true，否则返回false。我用c++实现了这个想法。

#include<iostream>
#include<string>

using namespace std;

bool palindromeExists(string s)
{
  int i = 0;
  int j = s.length()-1;
  while(i < j)
  {
      if(s[i] != s[j]) //first mismatch
          break;
      i++;
      j--;
  }

  int tempj = j-1; //remove s[j]
  int tempi = i;
  while(tempi < tempj)
  {
      if(s[tempi] != s[tempj])
          break;

      tempi++;
      tempj--;

  }

  if(tempi >= tempj) //palindrome found?
      return true;

  tempi = i+1; //remove s[i]
  tempj = j;
  while(tempi < tempj)
  {
      if(s[tempi] != s[tempj])
          return false;
      tempi++;
      tempj--;
  }
  return true;
}

int main()
{
  string s = "abca";
  if(palindromeExists(s))
      cout << "YES" << endl;
  else
      cout << "NO" << endl;
  return 0;
}

This should return true if the string is already a palindrome, or if it can be a palindrome after the removal of one character. I hope I didn't miss any corner cases.

如果字符串已经是回文，或者在删除一个字符后它可以是回文，则返回true。我希望我没有错过任何一个角落。

#2

You can refer complete program in c++ here. Input the string to get the index of character to be removed. String reversal is performed in palim() function. It returns -1 if string is already palindrome.

你可以在这里参考c++的完整程序。输入字符串以获取要删除的字符索引。字符串反转是在palim()函数中执行的。它返回-1，如果字符串已经回文。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

bool palim(string s)
{
    string s2;
    s2=string(s.rbegin(),s.rend());
    if(s2==s)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int check(string s)
{
    int x;
        if(s.length()%2==0)
        {
            for(int i=0,j=s.length()-1;i<s.length()/2,j>=s.length()/2;i++,j--)
            {
                if(s[i]!=s[j])
                {
                    string s1=s;
                    s1.erase(j,1);
                    if(palim(s1))
                    {
                        x=j;
                        break;
                    }
                    else
                    {
                        string s1=s;
                        s1.erase(i,1);
                        if(palim(s1))
                        {
                            x=i;
                            break;
                        }
                    }
                }
            }
        }
        else
        {

            for(int i=0,j=s.length()-1;i<s.length()/2,j>s.length()/2;i++,j--)
            {

                if(s[i]!=s[j])
                {
                    string s1=s;
                    s1.erase(j,1);

                    if(palim(s1))
                    {

                        x=j;
                        break;
                    }
                    else
                    {
                        string s1=s;
                        s1.erase(i,1);
                        if(palim(s1))
                        {
                            x=i;
                            break;
                        }
                    }
                }
            }
        }
        return x;
}

int main()
{

        string s;
        cin>>s;
        if(palim(s))
        {
            cout<<"-1"<<endl;
        }
        else
        {
            cout<<check(s)<<endl;
        }


    return 0;
}

#3

Similar to turingcomplete, but with sub functions:

类似于turingcomplete，但有子功能:

bool isPalindrome(std::string::const_iterator& start, std::string::const_iterator& end)
{
    while (start < end) {
        --end;
        if (*start != *end) {
            return false;
        }
        ++start;
    }
    return true;
}

bool test(const std::string& s)
{
    auto start = s.begin();
    auto end = s.end();

    if (isPalindrome(start, end)) {
        // If we remove the middle character of a palindrome,
        // We still have a palindrome.
        return true;
    }
    // Now test if there is a palindrome
    // if we skip the mismatch char from the start or from the end.
    auto start2 = start;
    auto end2 = end;
    ++start2;
    --end;
    return isPalindrome(start, end) || isPalindrome(start2, end2);
}

Live example

生活的例子