Leetcode #680.验证回文字串 Ⅱ

• • 算法：双指针
  • 思路
  • C++代码
  • Java代码
  • 总结

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

输入: s = "abca"
输出: true
解释: 你可以删除c字符。

输入: s = "abc"
输出: false

回味字串：即左右对称的字符串形如“aba、abcba”；
所以我们很容易想到用双指针来判断，每次只需要判断左右指针的值是否相等，如果能走到最后即为一个回文子串。
但是这仅仅是个开始，题目上说可以删除一个字符；

在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。

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

class Solution {
    public boolean validPalindrome(String s) {
        int n = s.length();
        int i = 0 , j = n - 1;
        while (i <= j ) {
            if (s.charAt(i) != s.charAt(j)) return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
            else {
                i ++ ;
                j -- ;
            }
        }
        return true;
    }
    public boolean isPalindrome (String s,int i,int j ) {
        while (i <= j) {
            if (s.charAt(i++) != s.charAt(j--)) return false ;
        }
        return true;
    }
}

本题关键在于对双指针的理解和灵活运用，尤其是处理删除一个字母时。