题目描述
给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串
样例
示例 1:
输入: "aba"
输出: True
示例 2:
输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
算法1
(双指针) $O(n)$
思路
依然是双指针算法,裸的判断回文串的进阶版本,对于裸的回文串,直接套双指针模板即可,而对于要删除一个字母的情况,当碰到不想等情况时候,可以删除i,也可以删除j因此有两种情况,而且只能删除一次,因此我们可以分别判断删除i和j,只要有一个变成回文串,就成立,而删除i,j结构基本类似,只是i,j起点不同,因此创建一个函数专门用来比较剩余部分是否是回文串。
C++ 代码
class Solution {
public:
bool validPalindrome(string s) {
int i=0,j=s.size()-1;
while(i<j){
if(s[i]!=s[j]) return isPalindrome(s,i+1,j)||isPalindrome(s,i,j-1);
i++,j--;
}
return true;
}
bool isPalindrome(string s,int i,int j){//判断回文串
while(i<j){
if(s[i]!=s[j]) return false;
i++,j--;
}
return true;
}
};