仅删除一个元素以制作字符串回文

Question

>我将得到字符串。我只能从中删除 1 个元素。删除它后，如果新字符串变成回文，我必须打印"是"否则"否"。

例如，我得到了一个字符串"abdbca"。在这里，我可以删除第 5 个索引"c"并使其成为回文，我必须打印"是"。另一方面，如果字符串是类似于"abcd"的东西，我不能通过只删除一个字符来使其成为回文。因此，我必须打印"否"。

我尝试这样做，但我的代码效率不够高。任何人都可以建议我一种有效的方法吗？我必须在不到 10^5 秒的时间内检查 2.5 长度的字符串。

我尝试这样做的方式如下所示：

#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("YESn");b++;break;}
        }
        //if(length <= res) printf("NOn");
        if(b==0) printf("NOn");
    }
    return 0;
}

Answer 1

由于您只需要删除一个字符，因此您可以通过修改回文检查来线性时间执行此操作。这个想法是，您将开头的字符与结尾的字符进行比较，并在第一次不匹配时停止。如果从不匹配的对中删除一个字符并获得回文，则返回 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;
}

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

Answer 2

你可以在这里引用 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;
}

Answer 3

类似于图灵完备，但带有子函数：

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);
}

现场示例