LeetCode.680.Valid Palindrome II 验证回文字符串 Ⅱ

题目描述

680 Valid Palindrome II
https://leetcode-cn.com/problems/valid-palindrome-ii/

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

---

解题过程

和判断字符串是否回文的方法一样，左右双指针 left,right 向中间移动并比较，当字符不同时，分别尝试跳过 left 指针下的字符和跳过 right 指针下的字符后比较剩余字符串是否回文，如果其中任意子串是回文则结果是回文。

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

private static class SolutionV202005 {
    public boolean validPalindrome(String s) {
        if (null == s || s.length() < 2) {
            return true;
        }
        char[] chars = s.toCharArray();
        for (int i = 0, j = chars.length-1; i <= j; i++, j--) {
            if (chars[i] != chars[j]) {
                // i+1 表示跳过 i 下标处的字符，j-1 表示跳过 j 下标处的字符，继续比较
                return isPalindrome(chars, i+1, j) || isPalindrome(chars, i, j-1);
            }
        }
        return true;
    }

    // 判断 chars[start...end] 是否回文
    private boolean isPalindrome(char[] chars, int start, int end) {
        for (int i = start, j = end; i <= j; i++, j--) {
            if (chars[i] != chars[j]) {
                return false;
            }
        }
        return true;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_680_ValidPalindrome2.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_680_ValidPalindrome2.java

---