一、题目

二、解题思路

        如果仅仅是验证是否为回文串，这比较简单，之前也讲过利用双指针验证回文串。然而这道题中，如果不是回文串，我们还能够删除一个字符，然后判断其是否为回文。原理依旧与之前相同，使用两个指针 left 和 right，从字符串的两边相向而行。倘若两个指针指向的字符不一样，那就说明不能构成回文串，此时我们可以删除一个字符。可以删除 left 指向的字符，也可以删除 right 指向的字符，如下图所示。

三、代码实现

#include <iostream>
#include <string>// 判断子串[left, right]是否是回文串
bool isPalindromic(const std::string& s, int left, int right) {while (left < right) {if (s[left++] != s[right--]) {return false;}}return true;
}// 判断字符串是否是有效的回文串
bool validPalindrome(const std::string& s) {// 左指针int left = 0;// 右指针int right = s.length() - 1;while (left < right) {// 如果两个指针指向的字符不一样，我们要删除一个，要么// 删除left指针指向的值，要么删除right指针指向的值if (s[left] != s[right]) {return isPalindromic(s, left + 1, right) || isPalindromic(s, left, right - 1);}left++;right--;}return true;
}int main() {std::string s = "abca";std::cout << std::boolalpha << validPalindrome(s) << std::endl;  // 输出: truereturn 0;
}