[刷题防痴呆] 0680 - 验证回文字符串 II (Valid

题目地址

https://leetcode.com/problems/valid-palindrome-ii/

题目描述

680. 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'.

思路

• 遇到不匹配的时候, 删除左边和删除右边都试一下. 只要有一种情况返回true. 就返回true.

关键点

代码

• 语言支持：Java

class Solution {
    public boolean validPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int left = 0;
        int right = s.length() - 1;
        char[] sc = s.toCharArray();

        while (left < right) {
            if (sc[left] == sc[right]) {
                left++;
                right--;
            } else {
                return isSubValid(sc, left + 1, right) || isSubValid(sc, left, right - 1);
            }
        }

        return true;
    }

    private boolean isSubValid(char[] sc, int left, int right) {
        while (left < right) {
            if (sc[left] != sc[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}