描述

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

示例

示例 1:

  1. 输入: s = "aba"
  2. 输出: true

示例 2:

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

示例 3:

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

提示

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

解题思路

  • 判断回文可以用双指针法，这里不再赘述，题目说明可以（最多）删除一个元素，那么当左右指针的字符不一样时，我们还需要接着判断删除左指针元素或者右指针元素后是否还成立。
  • 我们可以将判断回文的方法提出来，传参中包括左右指针，这样方便后续的判断。

代码

class Solution {
    private int len;
    public boolean validPalindrome(String s) {
        len = s.length();
        int left = 0, right = len - 1;
        while (left < right) {
            if (!(s.charAt(left) == s.charAt(right))) {
                return validPalindromeWithIndex(s, left + 1, right) || validPalindromeWithIndex(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }
    public boolean validPalindromeWithIndex(String s, int left, int right) {
        while (left < right) {
            if (!(s.charAt(left) == s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}