LeetCode 680. 验证回文串 II

约 5 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 字节 华为 百度 虾皮
标签
字符串 双指针 贪心

题目描述

✅ 680. 验证回文串 II

image-20260928220001727

题意分析

判断整个字符串能否在最多删除一个字符后成为回文，删除零个也允许。题目只包含小写英文字母，直接按下标比较字符即可，不需要过滤或转换大小写。

枚举每个删除位置再检查回文会重复扫描。回文要求两端字符依次对应，因此先用双指针从两端向内比较，把删除选择推迟到第一次不相等的位置，就只剩两个候选需要检查。

解法：双指针 + 一次跳过

核心思路

[!blue]

left、right 表示尚未检查的闭区间，区间外的字符已经成对匹配，删除机会仍未使用。

两端相等时，可以同时内缩而不删除。删除内部字符的可行方案显然仍被保留；对于长度至少为三的区间，若某个可行方案删除了端点，删后的回文要求该端点旁的内侧字符与它相同，改删这个相同的邻字符会得到同样的字符串。因此总能保留这对相等端点，把删除机会留给内部。长度不超过二且两端相等时，本身已经是回文。

第一次出现 s[left] != s[right] 时，删除区间内部的字符无法改变这对失配端点，所以唯一可能是删除左端或删除右端，分别对应 [left+1, right] 和 [left, right-1]。删除机会已用完，辅助函数只能检查剩余区间是否原样为回文，不能再次跳过字符。

任一候选为回文，就能与外侧已经匹配的字符一起组成完整回文；两个候选都失败，则不存在合法删除。可以先检查删左的候选，成功就短路返回；失败后仍必须检查删右，不能只凭下一对字符是否相等决定删哪边。

解题步骤

  • 左右指针从字符串两端开始；字符相等时同时向内移动。
  • 第一次失配时立即返回两个候选的结果：跳过左字符，或跳过右字符。
  • 辅助函数只判断指定闭区间是否为回文，不能再删除字符。
  • 主循环没有失配就返回 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)$。只有几个下标变量，全程在原字符串上按下标比较，没有构造任何子串或额外数组，辅助函数也是迭代写法，调用栈只有常数深度。

关键点总结

[!green]

  • 两端相等时，保留这一对不会排除所有可行方案，所以删除选择可以推迟到首次失配。
  • 唯一的分叉点是第一次失配处，此后删除机会已用尽，两支各自退化成纯回文判断，这正是复杂度停在 $O(n)$ 的原因。
  • 辅助函数里绝不能再写跳过逻辑，它的职责就是「这段区间原样是不是回文」。

易错点总结

[!yellow]

  • 只固定尝试删左或删右，会漏掉必须删除另一端的情况；第一条候选失败后还要检查另一条。
  • 内侧一对字符相等不能决定整段是否可行，候选区间必须完整判回文。
  • 辅助判断若再次允许删除，会错误接受需要多次删除的字符串。
  • 同时跳过两端等于删除两个字符，不符合最多一次。
  • 右指针从 length-1 开始，不能从字符串长度开始读取。
  • 指针相遇或交错时，剩余区间长度至多为一，已经是回文；这也覆盖单字符输入，以及两个字符失配后删掉任一端的情况。

相似题目

题目 难度 关联与区别
125. 验证回文串 简单 原题只需按过滤规则验证回文，本题在首次失配处增加一次删除选择。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/13215177
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！