125. Valid Palindrome (Two Pointers) 20.2.2 Easy

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: --------------------------------------------------------------- Two Pointers
--------------------------------------------------------------- O(n) T, O(1) S
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        left, right = 0, len(s) - 1
        while left < right:                                  # Can be "left < right" or "left <= right", here we choose the one in front
                                                             # because we do not need to check the centered element,
                                                             # it must be same as itself.
            while left < right and not s[left].isalnum():    # However, here must be left < right instead of left <= right
                                                             # Why ? Because for cases " ", 
                                                             # left <= right and not s[left].isalnum() will be satisfied:
                                                             # left == right == 1 and the space is not alphanumeric character
                                                             # then left += 1 will be execuated and increase left to 1 
                                                             # => s[left] will bring index out of range error
                                                             # isalnum() function check if the char is alphanumeric characters 
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():           # .lower() function is for "A man, a plan, a canal: Panama"
                                                              # where there is Upper P and lower p which should be considered the same
                return False
            left += 1
            right -= 1
        return True


Java Version:
class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        
        int head = 0, tail = s.length() - 1;
        char charHead, charTail;
        
        while (head <= tail) {
            charHead = s.charAt(head);
            charTail = s.charAt(tail);
            
            if (!Character.isLetterOrDigit(charHead)) {
                head ++;
            } else if (!Character.isLetterOrDigit(charTail)) {
                tail --;
            } else {
                if (Character.toLowerCase(charHead) != Character.toLowerCase(charTail)) {
                    return false;
                }
                head ++;
                tail --;
            }
        }
        return true;
    }
}