目录
3、剑指 Offer II 019. 最多删除一个字符得到回文
1、面试题 01.04. 回文排列
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
示例：
输入："tactcoa" 输出：true（排列有"tacocat"、"atcocta"，等等）
思路：可以重新排列，那就直接看字母的出现次数，也可以把相同的字母都替换为空格，如果最后剩下一个字母没被替换或者全被替换了，就可以组成回文串。
bool canPermutePalindrome(char* s){
// 把相同的字符都替换掉，如果最后没有或者有且仅有一个字符没被替换，返回true；
int len = strlen(s);
int num = len;
for(int i = 0; i < len; i++){
if(s[i] == ' ')
continue;
for(int j = 0; j< len; j++){
if(i == j)
continue;
if(s[i] == s[j]){
s[i] = ' ';
s[j] = ' ';
num -= 2;
break;
}
}
}
return num == 1 || num == 0;
}2、剑指 Offer II 018. 有效的回文
给定一个字符串
s，验证s是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。本题中，将空字符串定义为有效的 回文串 。
示例：
输入: s = "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串
思路：只考虑数字和字母，所以需要判断，双指针比较。
bool check(char s){
if(s >= 'a' && s <= 'z'
|| s >= 'A' && s <= 'Z'
|| s >= '0' && s <= '9')
return true;
return false;
}
bool isPalindrome(char * s){
int len = strlen(s);
int l = 0;
int r = len - 1;
while(l < r){
if(!check(s[l]))
l++;
else if(!check(s[r]))
r--;
else{
s[l] = s[l] <= 'Z' ? s[l] + 32 : s[l];
s[r] = s[r] <= 'Z' ? s[r] + 32 : s[r];
if(s[l] != s[r])
return false;
l++;
r--;
}
}
return true;
}3、剑指 Offer II 019. 最多删除一个字符得到回文
给定一个非空字符串
s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。示例：
输入: s = "aba" 输出: true
思路：前后双指针比较，如果碰到不相同的字符，分为两次情况解决：
- 前指针从当前位置移动，后指针从-1的位置移动
- 前指针从+1的位置移动，后指针从当前位置移动
通过比较前后指针的大小来判断是否将字符串全部遍历比较
bool validPalindrome(char * s){
int len = strlen(s);
int l = 0;
int r = len - 1;
int ok = 1;
while(l < r){
if(s[l] != s[r]){
int a = l;
int b = r - 1;
while(a < b && s[a] == s[b]){
a++;
b--;
}
if(a >= b)
return true;
a = l + 1;
b = r;
while(a < b && s[a] == s[b]){
a++;
b--;
}
if(a >= b)
return true;
return false;
}
else{
l++;
r--;
}
}
return true;
}4、1332. 删除回文子序列
给你一个字符串
s，它仅由字母'a'和'b'组成。每一次删除操作都可以从s中删除一个回文 子序列。返回删除给定字符串中所有字符（字符串为空）的最小删除次数。
「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。
「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。
示例：
输入：s = "ababa" 输出：1 解释：字符串本身就是回文序列，只需要删除一次。提示：
1 <= s.length <= 1000s仅包含字母'a'和'b'
思路：因为只包含a和b，所以字符串本身是一个回文串就返回1；如果不是，可以先删除所有a，在删除所有b，连续的a和连续的b也是回文串，所以最多也就两次操作，直接返回2。
int removePalindromeSub(char * s){
int len = strlen(s);
int l = 0;
int r = len - 1;
while(l < r){
if(s[l] != s[r])
return 2;
l++;
r--;
}
return 1;
}5、214. 最短回文串
给定一个字符串 s，你可以通过在字符串前面添加
字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例：
输入：s = "aacecaaa" 输出："aaacecaaa"
思路：将源字符串逆序保存得到一个新字符串，然后再将源字符串从后往前的按长度递增的把字符插在新字符串的末尾，然后判断是否回文串。
// 判断是否回文串
bool isPalindrome(char* s, int len){
int l = 0;
int r = len - 1;
while(l < r){
if(s[l] != s[r])
return false;
l++;
r--;
}
return true;
}
char * shortestPalindrome(char * s){
if(s == NULL)
return NULL;
int len = strlen(s);
if(isPalindrome(s, len)){
return s;
}
// 逆序保存源字符串
char* str = (char*)malloc(sizeof(char) * (2 * len + 1));
int top = 0;
for(int i = len - 1; i >= 0; i--){
str[top++] = s[i];
}
// 按长度循环，先1个字符，再2个、3个依次增大
for(int cnt = 1; cnt <= len; cnt++){
int tmp = top;
// 从后面开始
for(int i = len - 1, j = i - cnt, k = j + 1; k <= i; k++){
str[top++] = s[k];
}
if(isPalindrome(str, top)){
str[top] = '\0';
return str;
}
top = tmp;
}
str[top] = '\0';
return str;
}文首图片素材来自博客：《算法零基础100讲》(第26讲) 字符串算法(六) - 回文串_英雄哪里出来的博客-CSDN博客