[leetcode/lintcode 题解] 有效回文 II · Valid Palindrome II

【题目描述】

给一个非空字符串 s，你最多可以删除一个字符。判断是否可以把它变成回文串。

在线评测地址: https://www.lintcode.com/problem/valid-palindrome-ii/?utm_source=sc-bky-zq

【样例】

样例 1:

输入: s = "aba"

输出: true

解释: 原本就是回文串

样例 2:

输入: s = "abca"

输出: true

解释: 删除 'b' 或 'c'

样例 3:

输入: s = "abc"

输出: false

解释: 删除任何一个字符都不能使之变成回文串

【题解】

双指针算法。从两头走到中间，发现第一对不一样的字符之后，要么删左边的，要么删右边的。

class Solution {

    public boolean validPalindrome(String s) {

        int left = 0, right = s.length() - 1;

        while (left < right) {

            if (s.charAt(left) != s.charAt(right)) {

                break;

            }

            left++;

            right--;

        }

        if (left >= right) {

            return true;

        }

        return isSubPalindrome(s, left + 1, right) || isSubPalindrome(s, left, right - 1);

    }

    private boolean isSubPalindrome(String s, int left, int right) {

        while (left < right) {

            if (s.charAt(left) != s.charAt(right)) {

                return false;

            }

            left++;

            right--;

        }

        return true;

    }

}