验证回文字符串Ⅱ

给定一个非空字符串  s，最多删除一个字符。判断是否能成为回文字符串。
示例  1:
        输入:  "aba"
        输出:  True
示例  2:
        输入:  "abca"
        输出:  True
解释:  你可以删除c字符。
注意:字符串只包含从  a-z  的小写字母。字符串的最大长度是50000。

自我解答

        我是在字符串头尾使用双指针，向里对比，如果遇到不一样的，可以删除其中的一个，因此这里有两种删除方案。
        使用递归方式实现

class Solution4:
    def validPalindrome(self, s: str) -> bool:
        self.s = s
        return self.check(0, len(s)-1)

    def check(self, i, j, allow_del=1) -> bool:
        while i < j:
            if self.s[i] != self.s[j]:
                if allow_del:
                    return self.check(i+1, j, allow_del=0) or self.check(i, j-1, allow_del=0)
                else:
                    return False
            i += 1
            j -= 1
        return True

题解

        题解也是这个思路的，但不是用递归实现的,  减少了递归栈的维护,  但也差不多

class Solution3:
    def validPalindrome(self, s: str) -> bool:
        self.s = s
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return self.check(i+1, j) or self.check(i, j-1)
            i += 1
            j -= 1
        return True

    def check(self, i, j):
        while i < j:
            if self.s[i] != self.s[j]:
                return False
            i += 1
            j -= 1
        return True

原题链接：https://leetcode-cn.com/problems/valid-palindrome-ii