【算法】双指针算法 ( 有效回文串 II )

class Solution {

    /**
     * 给一个非空字符串 s，你最多可以删除一个字符。判断是否可以把它变成回文串。
     * @param s 给定的字符串 
     * @return 删除零个或一个字符后是否是回文串
     */
    public boolean validPalindrome(String s) {
        if (s == null) {
            return false;
        }

        // 先判定该字符串是否是回文串
        // 数组中 0 索引存放左指针, 1 索引存放右指针 
        int[] pointer = new int[2];
        findDifference(s, 0, s.length() - 1, pointer);
        if (pointer[0] >= pointer[1]) {
            return true;
        }

        // 如果字符串不是回文串, 则考虑删除左指针/右指针指向的字符, 再判定是否是字符串
        // 删除左指针指向的字符, 并验证是否是回文串
        return isPalindrome(s, pointer[0] + 1, pointer[1])
        		// 删除右指针指向的字符, 并验证是否是回文串  
                || isPalindrome(s, pointer[0], pointer[1] - 1); 
    }

    private void findDifference(String s, int left, int right, int[] result) {
        // 对比两字符是否相等, 如果相等, 指针向中间移动一位
        while (left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        // 设置返回值
        // 如果该字符串是回文串, 则左指针最后等于 ( 偶数个字符 ) 或者大于右指针 ( 奇数个字符 )
        // 如果该字符串不是回文串 , 则左右指针原封不动返回
        result[0] = left;
        result[1] = right;
    }

    private boolean isPalindrome(String s, int left, int right) {
        // 判定 s 字符串是否是回文串
        int[] pointer = new int[2];
        findDifference(s, left, right, pointer);
        return pointer[0] >= pointer[1];
    }
}

class Main {
    public static void main(String[] args) {
        System.out.println(
                new Solution().validPalindrome("abcnba")
        );
    }
}