【5.9】指针算法-双指针解验证回文字符串 Ⅱ

一、题目

二、解题思路

        如果仅仅是验证是否为回文串，这比较简单，之前也讲过利用双指针验证回文串。然而这道题中，如果不是回文串，我们还能够删除一个字符，然后判断其是否为回文。原理依旧与之前相同，使用两个指针 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;  // 输出: true
    return 0;
}