剑指 Offer II 019. 最多删除一个字符得到回文

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

示例 1:

输入: s = "aba"
输出: true
示例 2:

输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符
示例 3:

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

提示:

1 <= s.length <= 105
s 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/RQku0D
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回文字符串是指从左到右读取得到的字符与从右到左读取得到的字符一样的字符串。比如"上海自来水来自海上"。 我们可以使用双指针法遍历字符串，假如指针相遇了，说明字符串本身就是回文的；假如遇到两个字符不相等，那么可以尝试删除左侧的字符或者删除右侧的字符，继续尝试。假如依然失败，说明无法在最多删除一个字符的前提下使得字符串变成回文的。

  public boolean validPalindrome(String s) {
        char[] chs = s.toCharArray();
        int lo = 0;
        int hi = chs.length - 1;
        while(lo < hi){
            if (chs[lo] != chs[hi]) {
                break;
            }
            lo++;
            hi--;
        }
        if (lo >= hi) { //假如两个指针相遇了。奇数时有lo == hi，偶数时有lo > hi
            return true;
        }
        //将左侧的字符删掉试试
        boolean tryLeft = isPalindrome(chs, lo + 1, hi);
        if (tryLeft) {
            return true;
        }
        //将右侧的字符删掉试试
        boolean tryRight = isPalindrome(chs, lo, hi - 1);
        if (tryRight) {
            return true;
        }
        return false;
    }
    //判断是否是回文的典型方法，双指针比较。
    private boolean isPalindrome(char[] chs, int lo, int hi) {
        while(lo < hi){
            if (chs[lo] != chs[hi]) {
               return false;
            }
            lo++;
            hi--;
        }
        return true;
    }