680-验证回文字符串2

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。


示例 1:

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

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

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

提示:

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

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

首先我们可以判断字符串s是否是回文的，如果是直接返回true即可。 假如在判断s过程中，出现了两个字符不相等，那么我们可以选择跳过左侧字符(当做什么也没发生)或者跳过右侧字符(当做什么也没发生)继续尝试匹配得到最终结果。 写到这里，我忽然想到绿帽子侠，其经典语录：当然是选择原谅她！不过这道题最多是原谅一次。

比如abac,首尾是ac，不相等，那么可以跳过a比较bac或者跳过c比较aba。

第一种

 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，说明比较完了，s本身就是回文的
            return true;
        }
        //执行到这里，说明chs[lo] != chs[hi]，那么需要选择跳过哪一个
        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;
    }

第二种

第二种思路与第一种的类似，不过是在比较过程中提前约好是跳过左侧还是右侧。

 public boolean validPalindrome(String s) {
        if(s.length() == 1){
            return true;
        }
        char[] chs = s.toCharArray();
        if(validPalindrome(chs) || validPalindrome2(chs)){
            return true;
        }
        return false;
    }
    //该方法是选择跳过左侧，最多一个字符
    private boolean validPalindrome(char[] s){
        int i = 0 ; 
        int count = 0;
        int j = s.length - 1;
        while(i < j){
            if(s[i] != s[j]){
                if(count == 0){ //假如之前没有跳过左侧字符，那现在可以跳过一次，此时i++,j不变
                    i++;
                    count++;
                }else{
                    return false;
                }

            }else{
           i++;
            j--;
            }
           
        }
        return true;
    }
     private boolean validPalindrome2(char[] s){
        int i = 0 ; 
        int count = 0;
        int j = s.length - 1;
        while(i < j){
            if(s[i] != s[j]){
                if(count == 0){ //同上
                    j--;
                    count++;
                }else{
                    return false;
                }

            }else{
           i++;
            j--;
            }
           
        }
        return true;
    }

复杂度

时间复杂度均是O(n)，空间复杂度是O(1)