680. Valid Palindrome II.md

680. Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

代码

• For example, s = "acbba", whenever we find mismatch, we need to check the part "cbb", if "bb" or "cb" is palindrome (delete one left char or right char)

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        n = len(s)
        l, r = 0, n - 1
        while l < r:
            if s[l] != s[r]:
                extract_left = s[l+1:r+1]
                extract_right = s[l:r]
                return extract_left == extract_left[::-1] or \
                        extract_right == extract_right[::-1]
            else:
            	l, r = l + 1, r - 1
        return True