# 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

```python
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
```