LeetCode LCR 019. 验证回文串 II

2026-03-28 HGNULB 约 8 分钟

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

分类

LeetCode 简单 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 019. 验证回文串 II

题意分析

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

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

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

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

解法：双指针 + 一次跳过

核心思路

暴力做法是枚举删掉哪个字符，一共 $n$ 种选择，每种再花 $O(n)$ 判一次回文，总共 $O(n^2)$；$n$ 到 $10^5$ 时必然超时。

瓶颈在于：绝大多数删除位置根本不值得试。删掉一个原本两端已经配对成功的字符，不但对结果没有帮助，反而会把后面本已对齐的配对整体错开。

关键观察分两步。第一步，两端字符相等时可以放心内缩。设当前待判区间是 [l, r] 且 s[l] == s[r]，那么「[l, r] 至多删一个字符能成回文」与「[l+1, r-1] 至多删一个字符能成回文」是等价的。反方向显然成立；正方向可以这样看：若那次删除发生在区间内部，剩下的串首尾仍是 s[l] 和 s[r]，去掉这一对之后中间部分依然是回文，结论成立；若删的恰好是 s[l]（删 s[r] 同理），说明 s[l+1..r] 本身就是回文，那么把它的末位去掉得到的 s[l+1..r-1] 也只用了一次删除，同样满足要求。所以匹配即定死，不会错过任何解。

第二步，第一次失配时只有两个候选，而且每个候选内部不再分叉。走到 s[l] != s[r] 时，这一对字符必须由这唯一的一次删除来解决——如果把删除机会用在区间内部的其他位置，s[l] 与 s[r] 就仍然要互相匹配，而它们不相等，必定失败。于是候选只有「删 s[l]」和「删 s[r]」两个。而删除机会一旦用掉，剩下的区间 [l+1, r] 或 [l, r-1] 就必须本身是回文，不允许再删。这就是为什么只需要「分两支、各验一次」：分支数不是每次失配都翻倍，而是全程只在第一次失配处出现一次，之后是两段纯粹的线性扫描，完全不需要回溯或重试。

由此得到主循环的不变量：每轮开始时，[0, l-1] 与 [r+1, n-1] 已经逐位配对成功，删除机会尚未使用，原问题等价于「[l, r] 能否至多删一个字符成为回文」。循环正常结束时 [l, r] 已缩成空或单字符，说明一次都不用删，直接返回真。

解题步骤

左右指针分别放在字符串两端，循环条件写 left < right。两者相遇或交错就说明中间部分已经无需比较，此时一定是回文。

两端字符相等时同时内缩。上面第一步的论证保证了这一步是安全的，不会漏掉本可以通过删别处达成的解。

一旦失配就立即分成两支并 return，不再继续主循环。因为删除机会必须用在这里，主循环携带的「尚未删除」这条不变量到此已经失效，继续往下走就等于允许了第二次删除。

两支分别是「跳过左字符」即检查 [left + 1, right]，和「跳过右字符」即检查 [left, right - 1]，两者用逻辑或连接，任意一支为真即可返回真。顺序无所谓，短路求值只会少做一次扫描。

辅助函数是纯回文判断：双指针从两端向中间逐位比较，一旦不等立刻返回假，绝不能再有任何跳过逻辑。

以 s = "abbab" 走一遍（下标 0 到 4 依次是 a、b、b、a、b）：

left = 0、right = 4：s[0] = 'a' 与 s[4] = 'b' 不等，第一次失配就出现在起点，进入分支。

第一支「删左字符」检查区间 [1, 4]，即 "bbab"：s[1] = 'b' 与 s[4] = 'b' 相等，内缩；s[2] = 'b' 与 s[3] = 'a' 不等，辅助函数不允许再删，返回假。

第二支「删右字符」检查区间 [0, 3]，即 "abba"：s[0] = 'a' 与 s[3] = 'a' 相等，s[1] = 'b' 与 s[2] = 'b' 相等，指针交错退出，返回真。

两支取或得到真，对应的方案是删掉末尾那个 'b'，剩下 "abba"。这个例子刚好说明为什么两支都必须验：只看第一支会得出错误的假。

再看一个先内缩再分支的例子 s = "abca"：left = 0、right = 3 时 'a' 与 'a' 相等，内缩到 left = 1、right = 2；'b' 与 'c' 不等，第一支检查区间 [2, 2]，只有一个字符直接为真（对应删掉 'b' 得到 "aca"），短路返回真。

代码实现

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)$。主循环里两个指针相向而行，合计移动不超过 $n$ 步；失配之后最多再跑两次辅助函数，每次也是相向双指针、不超过 $n$ 步。三段加起来是 $3n$ 级别的常数倍，分支只发生一次，不会指数展开。

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

关键点总结

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

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

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

面试视角：最常见的追问是「推广到最多删 $k$ 个字符怎么办」。此时每次失配都要带着剩余次数分两支，朴素递归是 $O(2^k n)$，$k$ 较大时应改用区间 DP——「至多删 $k$ 个能成回文」等价于「原串长度减去最长回文子序列长度不超过 $k$」，也就是 516 题。能主动说出这条转化会明显加分。

易错点总结

错误写法：只验一支，例如失配后直接 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]，返回真；但这相当于删了两个字符，正确答案是假。

错误写法：失配后不 return，而是继续 left++; right--; 并用一个布尔标记记录「已删过」。这等价于在失配处同时丢弃两端，后果和上一条一样，s = "acbda" 会返回真。

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

错误写法：辅助函数里用「从 0 开始」的对称下标，比如 if (s.charAt(i) != s.charAt(right - i))，忘了区间起点不一定是 0。检查 [1, 3] 这类子区间时会比较到区间之外的字符，结果时对时错，是最难查的一类问题。

错误写法：枚举删除位置，对每个 $i$ 用 s.substring(0, i) + s.substring(i + 1) 拼出新串再判回文。逻辑正确但每次都要 $O(n)$ 地新建字符串，$n$ 达到 $10^5$ 时是 $O(n^2)$ 的时间和海量对象分配，必然超时。

相似题目

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