LeetCode 680. 验证回文串 II

2026-04-15 HGNULB 约 6 分钟

文章信息 9 个分类 4 个标签

分类

题目描述

✅ 680. 验证回文串 II

题意分析

给一个字符串，问它能否在最多删除一个字符之后成为回文串，返回布尔值。

「最多一个」这四个字是全题的核心，要拆成两层理解。第一层，删除的次数上限是 1，不是 2，也不是任意多——这直接排除了「两边同时跳过」这类写法。第二层，「最多」包含删 0 个，所以本身已经是回文的串直接返回真，不需要真的去删掉某个字符。

另一个信号是判定的对象是整个字符串，删除位置可以任选，删完之后剩下的字符按原顺序拼起来要求前后对称。字符串只含小写字母，长度上限是 $10^5$，这个规模明确否掉了 $O(n^2)$ 的枚举式做法。

边界情况：空串和单字符串天然是回文，返回真；长度为 2 的串无论两个字符是否相同都能通过（相同本来就是回文，不同则删掉任意一个变成单字符），可以用来快速检验写法是否过于保守。

解法：双指针 + 一次跳过

核心思路

枚举每个删除位置再判断回文需要 $O(n^2)$。真正需要考虑删除的位置只有第一次失配的两端，因此可以用双指针把候选压缩到两个。

两端相等时可以直接内缩：保留这一对不会消耗删除机会，也不会破坏内部可行解。若最终方案删除的恰是这对中的一个，那么去掉匹配的两端后，内部仍然至多删除一次即可成为回文。

第一次出现 s[left] != s[right] 时，这一对必须删掉一个，否则它们永远无法配对。只需检查 [left + 1, right] 与 [left, right - 1] 是否有一段本身就是回文；删除机会已经用完，辅助判断不能再次分支。

不变量是：主循环每轮开始时，窗口外的字符已经两两匹配，删除机会尚未使用，问题等价于判断当前 [left, right]。若指针相遇仍未失配，原串本身就是回文。

解题步骤

左右指针从字符串两端开始；字符相等时同时向内移动。

第一次失配时立即返回两个候选的结果：跳过左字符，或跳过右字符。

辅助函数只判断指定闭区间是否为回文，不能再删除字符。

主循环没有失配就返回 true。

例如 s = "abbab" 在首尾失配：跳过左端得到 "bbab"，不是回文；跳过右端得到 "abba"，是回文，所以结果为 true。这个例子也说明两支都必须检查。

代码实现

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--;
            } else {
                // 最多只能删除一个字符，所以只尝试两种跳过方式。
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
        }
        return true;
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

func validPalindrome(s string) bool {
    left := 0
    right := len(s) - 1
    for left < right {
        if s[left] == s[right] {
            left++
            right--
        } else {
            // 删除左字符或右字符，任意一种可行即可。
            return isPalindromeRange(s, left+1, right) || isPalindromeRange(s, left, right-1)
        }
    }
    return true
}

func isPalindromeRange(s string, left int, right int) bool {
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

复杂度分析

时间复杂度：$O(n)$。主循环和两次候选区间检查都是线性扫描，分支只发生一次，总工作量仍是线性级别。

空间复杂度：$O(1)$。只有几个下标变量，全程在原字符串上按下标比较，没有构造任何子串或额外数组，辅助函数也是迭代写法、不占栈。

关键点总结

两端相等就内缩这一步是可以严格证明的，不是拍脑袋的贪心：s[l] == s[r] 时保留这一对不会让可行解变得不可行。

唯一的分叉点是第一次失配处，此后删除机会已用尽，两支各自退化成纯回文判断，这正是复杂度停在 $O(n)$ 的原因。

辅助函数里绝不能再写跳过逻辑，它的职责就是「这段区间原样是不是回文」。

若推广为最多删除 $k$ 个字符，每次失配都可能继续分支；可改为区间 DP，或判断「字符串长度减最长回文子序列长度」是否不超过 $k$。

易错点总结

错误写法：只验一支，例如失配后直接 return isPalindrome(s, left + 1, right);。用 s = "abbab" 走：删左得到的区间 [1, 4] 是 "bbab"，不是回文，于是返回假；但删掉末尾的 'b' 后 "abba" 是回文，正确答案是真，这一支漏掉了唯一的解。

错误写法：用「看内侧字符谁能对上就删谁」的贪心，例如 if (s.charAt(left + 1) == s.charAt(right)) return isPalindrome(s, left + 1, right);。用 s = "abbab" 走：s[1] = 'b' 恰好等于 s[4] = 'b'，贪心认定该删左边，只检查 "bbab" 得到假，同样漏掉删右边的正确答案。局部相等并不能保证整段都能对齐。

错误写法：辅助函数里再允许一次删除（比如递归回主函数逻辑，或带了 deleted 标记却忘了置位）。用 s = "abcda" 走：两端 'a' 配对后 'b' 与 'd' 失配，分支进入 [2, 3] 即 "cd" 又失配，若还能再删一次就会返回真；而实际删任意一个字符都做不到回文，正确答案是假。

错误写法：失配时同时跳过两端，写成 return isPalindrome(s, left + 1, right - 1);。用 s = "acbda" 走：'a' 与 'a' 配对后 'c' 与 'd' 失配，同时跳过两边只剩单字符 [2, 2]，返回真；但这相当于删了两个字符，正确答案是假。

错误写法：右指针初始化为 s.length() 而不是 s.length() - 1。第一次取 s.charAt(right) 就下标越界，任何非空输入都直接抛异常。

错误写法：枚举每个删除位置并拼接新字符串。逻辑虽正确，但会产生 $O(n^2)$ 时间和大量临时对象。

相似题目

题目	难度	考察点
125. 验证回文串	简单	跳过非字母数字字符后的纯回文判定
LCR 019. 验证回文串 II	简单	同题不同题号，可直接对照复盘
234. 回文链表	简单	链表上没有随机访问时如何判回文
5. 最长回文子串	中等	以每个位置为中心向两侧扩展
647. 回文子串	中等	统计回文子串数量而非判定
516. 最长回文子序列	中等	区间 DP，对应「最多删 k 个」的推广