Archived

valid palindrome II

An old note — I haven't updated it since I wrote it.

This is one of those questions where i really get to see how quickly i'm currently progressing.

My most recent answer:

 1class Solution:
 2    def validPalindrome(self, s: str) -> bool:
 3        def is_pal(s, error=False):
 4            for i in range(len(s)//2):
 5                if s[i] != s[~i]:
 6                    if error:
 7                        return False
 8                    return is_pal(s[i+1:len(s)-i], True) or is_pal(s[i:len(s)-i-1], True)
 9            return True
10        return is_pal(s)

It's:

easy to read
simple yet sophisticated ([[list index complement]])
efficient (beats 75%)
in-place
uses recursion tastefully

my previous solution was a mess

This is in severe contrast with my previous solution, which was an utter mess. Hard to believe i wrote this only two weeks ago.

 1class Solution:
 2    def validPalindrome(self, s: str) -> bool:
 3        
 4        def try_left(l):
 5            if l + 1 == r:
 6                return True, l+1
 7            if s[l + 1] == s[r] and s[l + 2] == s[r - 1]:
 8                return True, l+1
 9            return False, l
10        
11        def try_right(r):
12            if r - 1 == l:
13                return True, r-1
14            if s[r - 1] == s[l] and s[r - 2] == s[l + 1]:
15                return True, r-1
16            return False, r
17        
18
19        l, r, skipped_one = 0, len(s)-1, False
20        while l <= r:
21            if s[l] == s[r]:
22                l += 1
23                r -= 1
24            else:
25                if skipped_one:
26                    return False
27                left_skip_ok, l = try_left(l)
28                if left_skip_ok:
29                    skipped_one = True
30                    continue
31                right_skip_ok, r = try_right(r)
32                if right_skip_ok:
33                    skipped_one = True
34                    continue
35                return False
36        return True