剑指 Offer II 019. 最多删除一个字符得到回文
地址:
该题与 相同
题目:
给定一个非空字符串 s,请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
示例 1:
示例 2:
示例 3:
提示:
思路:
看下几个示例:
回文:abba,abcba
可以看出只要是回文删除 1 次依旧是回文
非回文:abcb,bcba,cbbcc
左指针指向[0],右指针指向[len-1],调整一次左指针或右指针,剩下的如果是回文那么也可以
再来看个长点的示例:ebcbbececabbacecbbcbe
左指针调整可以[5] ->[6],右指针调整不可以 [15]->[14],总共调整次数也是一次
所以结论是,用双指针来扫描整个字符串,如果是回文 或者 通过一次调整后的子串也是回文,那么结果就是可以的,否则不可以
bool checksub(char *s, int i, int j) { bool ret = true; while(i < j) { if(s[i] != s[j]) { ret = false; break; } i++; j--; } return ret; } bool validPalindrome(char * s){ int slen = strlen(s); int i,j; int maxjudge = 0; bool ret = true; i = 0; j = slen - 1; while(i < j) { if(s[i] != s[j]) { if( checksub(s, i, j-1) || checksub(s, i+1, j) ) { ret = true; break; } else { ret = false; break; } } i++; j--; } return ret; }
上一篇:
IDEA上Java项目控制台中文乱码