日期: 2025 年 2 月 3 日

目标

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。

示例 3：

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

说明：

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

思路

判断给定字符串是否是回文，如果不是，能否删除任意一个字符使之变成回文。

当不满足回文条件时，分别考虑删掉其中一个字符，判断剩余子串是否是回文即可。

代码

/**
 * @date 2025-02-03 18:24
 */
public class ValidPalindrome680 {

    public boolean validPalindrome(String s) {
        int n = s.length();
        int i = 0;
        for (; i < n / 2; i++) {
            // 找到第一个不满足回文的字符下标
            if (s.charAt(i) != s.charAt(n - 1 - i)) {
                break;
            }
        }
        if (i == n / 2) {
            return true;
        }
        // 尝试删掉左边/右边字符判断剩余字符是否是回文
        boolean res = true;
        for (int j = i; j < n / 2; j++) {
            // 删掉 n - 1 - i，即 n - 2 - j
            if (s.charAt(j) != s.charAt(n - 2 - j)) {
                res = false;
            }
        }
        if (res) {
            return true;
        }
        // 这里是 j <= n /2，例如 abc，i + 1 指向 b
        for (int j = i + 1; j <= n / 2; j++) {
            // 这里是 n - 1 - i， 即 n - j，相当于删除了 i，但是右指针是不变的
            if (s.charAt(j) != s.charAt(n - j)) {
                return false;
            }
        }
        return true;
    }

}

性能