125 Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama"is a palindrome. "race a car"isnota palindrome.

Note: Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

The Idea: Confirm a regular palindrome, but ignore non alpha numeric characters.

Complexity: O(n) time and O(1) space

class Solution:
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """

        def isalpha_or_digit(char):
            return char.isalpha() or char.isdigit()

        left = 0
        right = len(s) - 1
        while left < right:
            # get the first valid left character
            while left < right and not s[left].isalnum():
               left += 1

            # get the first valid right character:
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1

        return True