📃 题目描述

题目链接：

• 剑指 Offer II 019. 最多删除一个字符得到回文 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 680. 验证回文字符串 Ⅱ - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

示例 1:

输入: s = "aba"
输出: true

示例 2:

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

🔔 解题思路

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // 删除 left 或者 right 指向的字符之后再判断能否形成回文
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }

            left ++;
            right --;
        }

        // 能够正常走出 while 循环，说明 s 本身就是一个回文串
        return true;
    }

    // 左闭右闭
    private boolean isPalindrome(String s, int left, int right) {
        if (left == right) {
            return true;
        }

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }

        return true;
    }
}

💥 复杂度分析

• 空间复杂度：O(1)
• 时间复杂度：O(N)