680. Valid Palindrome II

Description

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

 

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.

Solution

valid-palindrome-ii.py

class Solution:
    def validPalindrome(self, s: str) -> bool:
        valid = True
        n = len(s)
        i, j = 0, n - 1

        @cache
        def isPalindrome(i, j):
            nonlocal valid

            while i < j:
                if s[i] == s[j]:
                    i += 1
                    j -= 1
                else:
                    if valid:
                        valid = False
                        return isPalindrome(i + 1, j) or isPalindrome(i, j - 1)
                    else:
                        return False


            return i >= j

        return isPalindrome(i, j)