060 · Valid Palindrome II

algorithm
Published

July 17, 2026

My First Thoughts

嗯，这里接得很自然。

前面刚做过字符串里的双指针题，这道题本质上还是双指针练习，只是多了一个条件：

允许一次犯错。

也就是说，普通判断回文的时候，左右两边应该一直相等：

s[left] == s[right]

如果相等，就一起往中间走：

left += 1
right -= 1

这题的变化是，如果有一次不相等，也不一定马上失败。因为题目允许删除一个字符。

所以第一反应会是：

左右一起抵消，直到出现第二次犯错。

可以先写出一个 wrong_time，记录已经用掉了几次删除机会：

left = 0
right = len(s) - 1
wrong_time = 0

while left < right:
    if s[left] == s[right]:
        left += 1
        right -= 1

    elif s[left + 1] == s[right]:
        if wrong_time > 0:
            return False
        wrong_time += 1
        left += 2
        right -= 1

    elif s[left] == s[right - 1]:
        if wrong_time > 0:
            return False
        wrong_time += 1
        left += 1
        right -= 2

    else:
        return False

return True

这个想法里很重要的一点是对的：

只有在左右字符不相等的时候，才需要考虑删除一个字符。

如果删除左边的字符，那么下一步比较的就是：

s[left + 1] 和 s[right]

如果删除右边的字符，那么下一步比较的就是：

s[left] 和 s[right - 1]

所以这道题确实是在普通回文双指针的基础上，加一次容错。

Why That Is Not Enough

上面的方向是对的，但问题出在这里：

elif s[left + 1] == s[right]:

如果这个条件成立，代码会默认选择删除左边的字符。

但有时候，删除左边和删除右边在局部看起来都可以继续走。这个时候不能只根据代码顺序选一个。

比如：

s = "abbab"

一开始比较两端：

a 和 b

它们不相等。

如果看删除左边：

s[left + 1] == s[right]
b == b

局部看起来可以。

但如果真的删除左边的 "a"，剩下的是：

"bbab"

它不是回文。

而如果删除右边的 "b"，剩下的是：

"abba"

它是回文。

所以第一次不匹配时，真正的问题不是：

下一对字符能不能接上？

而是：

删除左边以后，剩下整个区间是不是回文？
或者删除右边以后，剩下整个区间是不是回文？

也就是说，第一次不匹配以后，不能贪心地选一个方向继续走。要检查两个完整的可能。

Final Idea

还是从普通回文判断开始。

准备两个指针：

left = 0
right = len(s) - 1

如果两边字符相等，就继续往中间走：

if s[left] == s[right]:
    left += 1
    right -= 1

真正关键的是第一次遇到不相等：

s[left] != s[right]

这时必须删除一个字符，才有可能继续成为回文。

删除选择只有两个：

  1. 删除左边的 s[left]，检查区间 left + 1 到 right
  2. 删除右边的 s[right]，检查区间 left 到 right - 1

只要其中一个区间是回文，答案就是 True。

所以可以写一个 helper：

def is_palindrome(l, r):

它只负责判断 s[l:r + 1] 这一段是不是回文。

然后主逻辑就是：

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

注意这里不需要继续维护 wrong_time。

因为一旦遇到第一次不匹配，删除机会就已经要被用掉了。后面只需要判断剩下的区间是不是一个普通回文。

Why It Works

如果字符串本身就是回文，那么左右指针会一直遇到相等的字符，最后 left >= right，返回 True。

如果中途第一次遇到：

s[left] != s[right]

那么这一对字符不可能同时保留。

为什么？

因为回文要求当前位置两边字符相等。现在它们不相等，而题目最多只允许删除一个字符，所以如果还有机会成功，只能删除这两个字符中的一个：

  • 删除左边的 s[left]
  • 删除右边的 s[right]

不可能删除中间别的字符来解决当前这一次不匹配。

所以只需要检查：

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

如果其中一个为真，说明删除对应那个字符以后，剩下部分可以成为回文。

如果两个都为假，说明不管删左还是删右，剩下部分都不是回文。由于只能删一个字符，所以答案就是 False。

Code

def validPalindrome(s):
    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    left = 0
    right = len(s) - 1

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

    return True

Complexity

Time \(O(n)\) - 主循环会扫描一部分字符串；第一次不匹配后，最多再检查两个剩余区间，总体仍然是线性时间
Space \(O(1)\) - 只使用了几个指针变量，没有创建额外数组

Takeaway

当双指针遇到一次允许容错的不匹配时，不要只看“跳过哪边以后下一对能不能相等”。真正要验证的是：跳过左边后的整个剩余区间，或者跳过右边后的整个剩余区间，是否有一个是完整回文。

← Quiz