680. Valid Palindrome II

string,logic

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

• 1 <= s.length <= 105

• s consists of lowercase English letters.

分析

错误思路：贪心思想，左边删掉可以的话就继续，但是事实上可能后续失败

但是其实删掉右边可能就可以了，但因为左边已经走下去了，无法验证了

字符串结构分析

Copy

Index: 0 1 2 3 4 5 6 7 8
Char: c u p u u p u c u

• 初始时 l=0（'c'），r=8（'u'），发现 s[0] != s[8]（'c' != 'u'）。

• 原代码会尝试跳过左边或右边的字符：

  • 检查 s[l+1] == s[r]：s[1] = 'u' vs s[8] = 'u' → 匹配，于是跳过 s[0] 的 'c'，移动指针 l=2，r=7。

  • 接下来比较 s[2]（'p'）和 s[7]（'c'），发现不匹配，但此时 change=1（已跳过一次），直接返回 False。

问题根源

原代码在第一次跳过 'c' 后，剩余的字符串是 "upuupuc"，它本身不是回文（因为 'p' != 'c'），但原代码没有全局验证跳过后的子串是否整体回文，而是仅检查了相邻字符，导致误判。

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

        return True