680. 验证回文串 II

题目链接（简单）

题目描述

给定一个字符串 s，最多 可以从中删除一个字符，判断 s 能否成为回文字符串。

能则返回 true，否则返回 false。

数据范围：

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

核心思路

判断回文最自然的方式是双指针：左指针 left 从头部、右指针 right 从尾部，向中间靠拢，逐对比较字符。

• 若所有对应字符都相等，原串本身就是回文，直接返回 true；
• 若某一对 s[left] != s[right]，说明原串不是回文，需要借助「删除一个字符」来补救。

关键分析：不匹配时，删除必须发生在这两个字符之一

假设第一次不匹配发生在 left 和 right：

s[left] != s[right]

此时这两个字符至少有一个必须被删除，否则它们会永远卡在两端，无论删中间哪个字符，都无法构成回文。

而题目只允许删一个字符，所以只有两种选择：

1. 删除 s[left]：判断剩余子串 s[left+1 .. right] 是否是回文；
2. 删除 s[right]：判断剩余子串 s[left .. right-1] 是否是回文。

只要其中一种成立，就返回 true；两种都不成立，返回 false。

为什么不需要考虑其他删除位置

如果删的是中间某个字符，s[left] 和 s[right] 仍然不相等，它们依然卡在两端，字符串仍然不是回文。所以删除必须发生在这两个不匹配的字符之一上，没有第三种可能。

方法：双指针 + 贪心分支

思路及解法

1. 双指针 left = 0、right = n - 1，向中间扫描；
2. 若 s[left] == s[right]，两指针同时内移，继续；
3. 若 s[left] != s[right]，进入分支：
   • 检查 s[left+1 .. right] 是否为回文，或
   • 检查 s[left .. right-1] 是否为回文；
   • 任意一个成立则返回 true，否则返回 false；
4. 若循环正常结束（没有遇到不匹配），返回 true。

代码

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(l: int, r: int) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
            left += 1
            right -= 1

        return True

复杂度分析

• 时间复杂度：$O(n)$。
  • 外层 while 最多扫描 $O(n)$ 个字符；
  • 遇到不匹配时，is_palindrome 最多被调用两次（or 可能短路），每次最多扫描 $O(n)$ 个字符；
  • 总时间复杂度为 $O(n)$。
• 空间复杂度：$O(1)$。只使用了几个指针变量，is_palindrome 是迭代实现，不涉及递归栈。

关键细节

1. 为什么只需要检查两种删除方案

第一次不匹配的位置 left、right 上的字符，必须删掉其中一个，否则它们永远无法配对。删除其他位置不会改变这个矛盾，所以只有两种可能，不需要枚举所有删除位置。

2. or 的短路特性

return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)

若第一种方案返回 True，第二种不会再执行，节省一次 $O(n)$ 的扫描。最坏情况下两次都执行，仍是 $O(n)$。

3. 循环正常结束即返回 True

若 while 循环完整结束都没有遇到不匹配，说明原串本身就是回文，不需要删除任何字符，直接返回 True。

4. 边界情况

• 长度为 1 的字符串：循环不执行，直接返回 True；
• 长度为 2 且字符相同：循环一次，left == right 后退出，返回 True；
• 长度为 2 且字符不同：进入分支，两个子串都是长度 1（回文），返回 True。

总结

• 核心观察：第一次不匹配时，删除必须发生在 left 或 right 之一；
• 双指针扫描：匹配时同时内移，不匹配时尝试两种删除方案；
• 辅助函数 is_palindrome(l, r)：判断子串 s[l..r] 是否回文；
• 时间复杂度 $O(n)$，空间复杂度 $O(1)$；
• 通用套路：「最多删一个字符判断回文」→ 双指针 + 两种分支尝试。

相关题目

• LC 125. 验证回文串（基础双指针）
• LC 647. 回文子串（统计所有回文子串）
• LC 5. 最长回文子串（中心拓展 / DP）
• LC 1216. 验证回文字符串 III（最多删 k 个字符，DP）