valid palindrome II

🏠

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

 1 class 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:

• 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.

 1 class 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