1
# Runtime: 9164 ms (Top 5.04%) | Memory: 645.8 MB (Top 5.21%)
2
class Solution:
3
    def validPalindrome(self, s: str) -> bool:
4
        has_deleted = False
5

6
        def compare(s, has_deleted):
7

8
            if len(s) <= 1:
9
                return True
10

11
            if s[0] == s[-1]:
12
                return compare(s[1:-1], has_deleted)
13
            else:
14
                if not has_deleted:
15
                    return compare(s[1:], True) or compare(s[:-1], True)
16
                else:
17
                    return False
18

19
        return compare(s, has_deleted)