[String] LC 680. Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/

Goal

• To verify if a string is a palindrome; maximum of 1 character difference is allowed

Strategy

• We need a way to keep track of the usage of the deletion of at most one character
• Create a flag variable, and use recursion to keep track of the value of the variable
• Increment l+1, decrement r-1, and compare s[l] == s[r] in order to keep track of the palindrome condition; once the condition failed, check the following
• In the cases that both recursive_helper(s, l+1, r, True) AND recursive_helper(s, l, r-1, True) returns False, the input string is not a palindrome

Highlights

• Two-pointers
• Simple Recursion

Code

class Solution:
    def validPalindrome(self, s: str) -> bool:
        l, r = 0, len(s)-1
        
        def helper(s,l,r,flag):
            while l<r:
                if s[l]==s[r]:
                    l+=1
                    r-=1
                else:
                    if flag:
                        return False
                    else:
                        return helper(s,l+1,r,True) or helper(s,l,r-1,True)
            return True
        
        return helper(s,l,r,False)

Time & Space

• Time: The maximum depth of recursion is O(N/2) → O(N)
• Space: O(1) since we are not creating extra objects