125. Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l,r = 0, len(s)-1
        while l < r:
            while not s[l].isalnum() and l<r:
                l+=1
            while not s[r].isalnum() and l<r:
                r-=1
            if s[r].lower() != s[l].lower():
                return False
            l+=1
            r-=1
        return True

Time Complexity: O(n)

Space Complexity: O(1)

Explanation

THe idea is to ignore all non-alphanumeric characters by pushing the l&r pointers until one of those characters is found.

And when performing comparisons, use the loewrcase version of each character.