LeetCode 每日一题 680. 验证回文串 II

680. 验证回文串 II

难度 简单

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

题目描述：可以删除一个字符，判断是否能构成回文字符串。

所谓的回文字符串，是指具有左右对称特点的字符串，例如 "abcba" 就是一个回文字符串。

使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。

代码:

class Solution {
public:
    bool valid(string s, int i, int j)
    {
        while(s[i] == s[j] && i < j) i++, j--;
        return i == j || (i - 1) == j;
    }
    bool validPalindrome(string s) {
        
        int i = 0, j = s.size() - 1;
        while(s[i] == s[j] && i < j) i++, j--;
        if (i == j || (i - 1) == j) return true;
        if (s[i + 1] == s[j])
            if (valid(s, i + 1, j)) return true;
        if (s[i] == s[j - 1])
            if (valid(s, i , j - 1)) return true;
        return false;
    }
};