LC 0125 0680 [E] [E] Valid Palindrome I II - ALawliet/algorithms GitHub Wiki

• skip the invalids
• check palindrome with lowercase
• iterate pointers

---

I

class Solution:
    def isPalindrome(self, s: str) -> bool:
        n = len(s)
        i, j = 0, n - 1
        
        while i < j:
            # skip non-letters/numbers
            while i < j and not s[i].isalnum(): i += 1
            while i < j and not s[j].isalnum(): j -= 1
                
            if s[i].lower() == s[j].lower():
                i += 1 ; j -= 1
            else:
                return False
            
        return True

• use 2 pointers for palindrome, and recursively check if still palindrome if removed 1 letter at a time from each side
• helper function has same structure to main function just different return if no char match

T: O(n)
S: O(1)

---

gotchas:

• we can return because we check it is a palindrome after deleting AT MOST ONE character from it
• we create a helper function instead of recursing on the main one because it doesn't accept i, j

II

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def valid(i, j):
            while i < j:
                if s[i] == s[j]:
                    i += 1 ; j -= 1
                else:
                    return False #
            return True

        n = len(s) #
        i, j = 0, n - 1 #
        while i < j:
            if s[i] == s[j]:
                i += 1 ; j -= 1
            else:
                return valid(i+1, j) or valid(i, j-1) #
        return True