Valid Palindrome详解编程语言

Given a string, determine if it is a palindrome, 
considering only alphanumeric characters and ignoring cases. 
 
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. 
 
Challenge 
O(n) time without extra memory.

class Solution { 
public: 
    /** 
     * @param s A string 
     * @return Whether the string is a valid palindrome 
     */ 
    bool isPalindrome(string& s) { 
        if (s.empty()) return true; 
 
        int l = 0, r = s.size() - 1; 
        while (l < r) { 
            // find left alphanumeric character 
            if (!isalnum(s[l])) { 
                ++l; 
                continue; 
            } 
            // find right alphanumeric character 
            if (!isalnum(s[r])) { 
                --r; 
                continue; 
            } 
            // case insensitive compare 
            if (tolower(s[l]) == tolower(s[r])) { 
                ++l; 
                --r; 
            } else { 
                return false; 
            } 
        } 
 
        return true; 
    } 
};

public class Solution { 
    /** 
     * @param s A string 
     * @return Whether the string is a valid palindrome 
     */ 
    public boolean isPalindrome(String s) { 
        if (s == null || s.isEmpty()) return true; 
 
        int l = 0, r = s.length() - 1; 
        while (l < r) { 
            // find left alphanumeric character 
            if (!Character.isLetterOrDigit(s.charAt(l))) { 
                l++; 
                continue; 
            } 
            // find right alphanumeric character 
            if (!Character.isLetterOrDigit(s.charAt(r))) { 
                r--; 
                continue; 
            } 
            // case insensitive compare 
            if (Character.toLowerCase(s.charAt(l)) == Character.toLowerCase(s.charAt(r))) { 
                l++; 
                r--; 
            } else { 
                return false; 
            } 
        } 
 
        return true; 
    } 
}