leetcode_680 验证回文串
1. 题意
在最多去掉一个字符的情况下，判断一个字符串是否是回文串。
2. 题解
双指针
两个指针i j分别指向字符串开头和结尾，如果相同则同时向中间移动；如果不同则判断剩下的字符串，去掉头或者去掉尾能否成一回文串。
i = 0
j = sz - 1
while i < j:
if s[i] == s[j]
i++,j--;
else
return isPalindrome(s, i+1,j) || isPalindrome(s,i,j-1);
return true;
- C++
class Solution {
public:
bool check(const string &s, int i, int j) {
while (i < j) {
if (s[i] != s[j])
return false;
i++,j--;
}
return true;
}
bool validPalindrome(string s) {
int sz = s.size();
int i = 0;
int j = sz - 1;
while (i < j) {
if (s[i] != s[j])
break;
i++;
j--;
}
if (i >= j)
return true;
return check(s, i, j - 1) || check(s, i + 1, j);
}
// abbda
//abcdca
// acac
};