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" is not a 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.

判断string是否是Palindrome，此题只考虑数字字母，字母不用区分大小写，无视所有符号和空格。所以我们可以用左右两个指针边检测边压缩，一直到两个指针重合。

Character.isDigit(...) 和 Character.isLetter(...)这两个函数帮我们省去了很多麻烦。

public class Solution {
     //Time: O(n) Space: O(1)
     public boolean isPalindrome(String s) {
         if (s == null || s.length() <= 1) {
             return true;
         }
         
         s.trim();
         int left = 0;
         int right = s.length() - 1;
         while (left < right) {
             while (left < s.length() && !Character.isDigit(s.charAt(left)) && 
                    !Character.isLetter(s.charAt(left))) {
                 left++;           
             }
             if (left == s.length()) {
                 break;
             }
             while (right >= 0 && !Character.isDigit(s.charAt(right)) && 
                    !Character.isLetter(s.charAt(right))) {
                 right--;           
             }
             if (right < 0) {
                 break;
             }
             if (Math.abs(s.charAt(left) - s.charAt(right)) != 0 && 
                 Math.abs(s.charAt(left) - s.charAt(right)) != 'a' - 'A') {
                 return false;        
             }
             left++;
             right--;
         }
         return true;
     }
}