valid_palindrome_ii

View Source

 1# @leet start
 2class Solution:
 3    def validPalindrome(self, s: str) -> bool:
 4        """
 5        This question asks us to find if a string is a palindrome if you can delete
 6        up to one character.
 7
 8        We can do this by checking if a palindrome is valid from the inside or
 9        outside, and then if there's a character that breaks the palindromic
10        invariant, we can skip it, by skipping the current character.
11        """
12
13        def is_valid(l, r, skipped):
14            while l < r:
15                if s[l] != s[r]:
16                    if skipped:
17                        return False
18                    return is_valid(l, r - 1, True) or is_valid(l + 1, r, True)
19                l += 1
20                r -= 1
21            return True
22
23        return is_valid(0, len(s) - 1, False)
24
25
26# @leet end
27
28
29def test():
30    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def validPalindrome(self, s: str) -> bool:
 5        """
 6        This question asks us to find if a string is a palindrome if you can delete
 7        up to one character.
 8
 9        We can do this by checking if a palindrome is valid from the inside or
10        outside, and then if there's a character that breaks the palindromic
11        invariant, we can skip it, by skipping the current character.
12        """
13
14        def is_valid(l, r, skipped):
15            while l < r:
16                if s[l] != s[r]:
17                    if skipped:
18                        return False
19                    return is_valid(l, r - 1, True) or is_valid(l + 1, r, True)
20                l += 1
21                r -= 1
22            return True
23
24        return is_valid(0, len(s) - 1, False)

def validPalindrome(self, s: str) -> bool: View Source

 4    def validPalindrome(self, s: str) -> bool:
 5        """
 6        This question asks us to find if a string is a palindrome if you can delete
 7        up to one character.
 8
 9        We can do this by checking if a palindrome is valid from the inside or
10        outside, and then if there's a character that breaks the palindromic
11        invariant, we can skip it, by skipping the current character.
12        """
13
14        def is_valid(l, r, skipped):
15            while l < r:
16                if s[l] != s[r]:
17                    if skipped:
18                        return False
19                    return is_valid(l, r - 1, True) or is_valid(l + 1, r, True)
20                l += 1
21                r -= 1
22            return True
23
24        return is_valid(0, len(s) - 1, False)

This question asks us to find if a string is a palindrome if you can delete up to one character.

We can do this by checking if a palindrome is valid from the inside or outside, and then if there's a character that breaks the palindromic invariant, we can skip it, by skipping the current character.

def test(): View Source

30def test():
31    assert 2 + 2 == 4