leetcode_680 验证回文串

1. 题意

在最多去掉一个字符的情况下，判断一个字符串是否是回文串。

2. 题解

双指针
两个指针i j分别指向字符串开头和结尾，如果相同则同时向中间移动；如果不同则判断剩下的字符串，去掉头或者去掉尾能否成一回文串。

	i = 0j = 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
};