680.验证回文字符串 Ⅱ

原题地址

常规的判断回文串方法，一般就是双指针从两侧向中间夹，或者是逆序复制字符串，看和原字符串是否相等。而这道题，在普通回文串的基础上，加了可以删除最多一个字符这个条件。

这样我们可以利用这个条件，来把问题转化为普通的回文串问题。

• 初始化两个指针 low 和 high 分别指向字符串的第一个字符和最后一个字符。
• 每次判断两个指针指向的字符是否相同，如果相同，则更新指针，令 low = low + 1 和 high = high - 1，然后判断更新后的指针范围内的子串是否是回文字符串。
• 如果两个指针指向的字符不同，则两个字符中必须有一个被删除，此时我们就分成两种情况：即删除左指针对应的字符，留下子串 s[low + 1], s[low + 1], …, s[high]，或者删除右指针对应的字符，留下子串 s[low], s[low + 1], …, s[high - 1]。
• 此时这两个子串的判断，就可以采取普通回文串的方式了。
• 当这两个子串中至少有一个是回文串时，就说明原始字符串删除一个字符之后就以成为回文串。

Python代码

def validPalindrome(self, s: str) -> bool:
    def isPalindrome(l, h):
        while l <= h:
            if s[l] != s[h]:
                return False
            l += 1  
            h -= 1
        return True
    low, high = 0, len(s)-1
    while low <= high:
        if s[low] == s[high]:
            low += 1
            high -= 1
        else:
            return isPalindrome(low, high-1) or isPalindrome(low+1, high)
    return True

时间复杂度O(n)

空间复杂度O(1)