C语言 判断能否通过去掉0个或1个字符使得字符串成为回文串

C语言 判断能否通过去掉0个或1个字符使得字符串成为回文串

两种思路，第一种是枚举，你首先判断原串是否是回文串，不是的的话就枚举每个可能插入的位置，插入一个字符X，看看是否构成回文串（最多枚举81个位置）。字符X如何确定？无非是看在原串中出现了哪些字符，对这些字符进行枚举。（最多枚举80个，你可以利用一些条件缩小枚举范围）如果字符串长度为n，本算法复杂度为O(n^3)。由于本问题字符串最多不超过80个字符，规模比较小，所以不会超时。
第二种方法，我自己猜的，你可以试一下对不对。求出原串 a 的逆串 b，保存起来。记字符串 a 的长度为 l1，对字符串 a 和 b 求一次最长公共子序列长度，记为 l2，如果 l1-l2 的结果是 0 或者 1 的话，就输出 Y。

多定义一个指针同时判断不久行了。

#include <stdio.h>
#include <string.h>
bool Isrev(char *s) {
int i,n = strlen(s);
for(i = 0;i < (n + 1)/2;i++) if(s[i] != s[n - i - 1]) return false;
return true;
}
int main() {
char s[81],t[81],ch;
int len;
printf("请输入一个串:");
gets(s);
if(Isrev(s)) printf("%s是回文串!\n\n",s);
else {
len = strlen(s);
for(int i = 0; i < len; ++i) {
strcpy(t,s);
ch = t[i];
for(int j = i; j < len; ++j) t[j] = t[j + 1];
if(Isrev(t)) {
printf("去除字符第%d个'%c'后,%s是回文串!\n\n",i + 1,ch,t);
return 0;
}
}
printf("%s不是回文串!\n\n",s);
}
return 0;
}

ms可以O(n)
012。。。ii+1...... j-1 j .....n
在满足i+1<j-1的情况下，两头往中间扫
a[i]==a[j]，则继续，
如a[i]==a[j-1]或者a[i+1]=a[j]则需要插入，做一个需要插入的标记（如计数），同时移动相应的指针跳过不等的字符，继续比下去，直到两指针的前沿相遇并穿过（前沿能相遇并穿过说明小于4个字符了）。
按大概思路简单试了下，仅供参考：
#include "stdio.h"
#include "string.h"
int main()
{
int n;
char a[100]="abca";
int i,j,flag;
n=strlen(a);
i=0;
j=n-1;
flag=0; // characters qty need inserted
while ( (flag<2) // only need 0 or 1 character
&& ((i+1)<=(j-1)) // have character to compare
)
{
if (a[i]==a[j]) {i++; j--;}
else if (a[i]==a[j-1]) {flag++; i++; j-=2;}
else if (a[i+1]==a[j]) {flag++; i+=2; j--;}
else flag=2;
}
if (flag<2) printf("Y");
else printf("N");
return 0;
}

比如输入字符串存入str[]；
strlen()求长度，设为n;
for(int i=0; i<n/2; i++)
{
比较str[i]与str[n-1-i]//字符串从0开始
不一致即不可能；设置一个不一致的标记；
}
如果不一致的标记为0，就表示完全可以，或者中间只差一个字符，--〉ok