Leetcode680：验证回文串 II

题目描述：

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

代码思路：

1. 定义辅助函数 is_palindrome：

   • 这个函数用于检查一个字符串的子串是否是回文。
   • 它接受三个参数：子串 sub_s，子串的左边界 left，和子串的右边界 right。
   • 使用一个 while 循环，当左边界小于右边界时，比较左右边界的字符是否相等。
   • 如果字符不相等，返回 False，表示子串不是回文。
   • 如果字符相等，则移动左右边界向内收缩，继续比较。
   • 如果循环结束都没有返回 False，则说明子串是回文，返回 True。

2. 主函数 validPalindrome：

   • 这个函数接受一个字符串 s 作为参数，用于判断该字符串是否是有效的回文字符串。
   • 初始化两个指针 left 和 right 分别指向字符串的开头和结尾。
   • 使用一个 while 循环，当左指针小于右指针时，执行以下步骤：
     • 比较左右指针指向的字符是否相等。
     • 如果字符相等，则移动左右指针向内收缩，继续比较。
     • 如果字符不相等，说明当前字符串不是直接回文，但可能是通过删除一个字符后成为回文。
     • 调用 is_palindrome 函数检查两种情况：
       • 删除左指针指向的字符后，剩余的子串是否是回文。
       • 删除右指针指向的字符后，剩余的子串是否是回文。
     • 如果上述两种情况中任何一种返回 True，则说明原字符串是有效的回文字符串（即可以通过删除最多一个字符成为回文），返回 True。
     • 如果循环结束都没有发现字符不相等的情况，说明字符串本身就是回文，返回 True。

代码实现：

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

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