有效回文串（二）

https://www.lintcode.com/problem/891/description?utm_source=sc-libao-ztt

描述

给一个非空字符串 s，你最多可以删除一个字符。判断是否可以把它变成回文串。

1. 给定的字符串只包含小写字母

2. 字符串的长度最大为 50000

样例

样例 1:

输入: s = "aba"输出: true解释: 原本就是回文串

样例 2:

输入: s = "abca"输出: true解释: 删除 'b' 或 'c'

样例 3:

输入: s = "abc"输出: false解释: 删除任何一个字符都不能使之变成回文串

分析：

双指针，遇到第一对不相等的字符，去掉左边或者右边。

class Solution:
    """
    @param s: a string
    @return: whether you can make s a palindrome by deleting at most one character
    """
    def valid_palindrome(self, s: str) -> bool:
        # Write your code here
        def is_valid(l,r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True
        l, r = 0, len(s) - 1
        while l < r:
            if s[l] != s[r]:
                return is_valid(l+1,r) | is_valid(l, r-1)
            l += 1
            r -= 1
        return True