Problem description:

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

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

Example 1:
Input: “A man, a plan, a canal: Panama”
Output: true

Example 2:
Input: “race a car”
Output: false

Solution:

Use two pointers to solve this question.
isalnum can check if the character is numeric or alphabetic.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isPalindrome(string s) {
        int left= 0, right= s.length()-1;
        
        while(left< right){
            if(!isalnum(s[left])) left++;
            else if(!isalnum(s[right])) right--;
            else{
                if(tolower(s[left])!= tolower(s[right]))
                    return false;
                else
                    left++; right--;
            }
        }
        return true;
    }
};

Python solution, also use two pointers to solve.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isPalindrome(self, s: str) -> bool:
        p, q = 0, len(s)-1
        while p < q:
            while p< q and not s[p].isalnum():
                p+=1
            while p< q and not s[q].isalnum():
                q-=1
                
            if s[p].lower() != s[q].lower():
                return False
            p+=1; q-=1
        return True

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://goo.gl/vyjCpj