680. 验证回文字符串 Ⅱ
难度简单311
给定一个非空字符串
s
,最多删除一个字符。判断是否能成为回文字符串。
示例 1:
示例 2:输入: "aba" 输出: True
注意:输入: "abca" 输出: True 解释: 你可以删除c字符。
- 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
双指针法
因为这有可能需要删除一个字母,所以我们把验证是否是回文串写进一个函数里面。还是按之前的双指针方法判断字母是否相同,如果遇到一个不相同时,此时就出现了可能需要删除的字母。
但删除次数只有一个,要么是当前左指针或右指针,因此在这里调用之前写好的回文串check函数,把索引相应的写入即可。这样的好处是用函数的参数索引可以同时判断两个位置的字母是否需要删除。
class Solution {
public:
bool validPalindrome(string s) {
int left = 0, right = s.length()-1;
while(left < right){
if(s[left] == s[right]){
left++;
right--;
}
else{
return check(s, left+1, right) || check(s, left, right-1);
}
}
return true;
}
bool check(string& s, int left, int right){
while(left < right){
if(s[left] != s[right]){
return false;
}
left++;
right--;
}
return true;
}
};