Question

link

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.

Stats

Frequency 5
Difficulty 2
Adjusted Difficulty 1
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Wow, it’s frequency 5!

This is a very classic and easy question.

Code

public boolean isPalindrome(String s) {
    int len = s.length();
    s = s.toLowerCase();
    int left = 0, right = len - 1;
    while (left < right) {
        while (left < len && !isAlphanumeric(s.charAt(left)))
            left ++;
        while (right >= 0 && ! isAlphanumeric(s.charAt(right)))
            right --;
        if (left == len && right == -1) return true;
        if (left == len || right == -1) return false;
        if (s.charAt(left) != s.charAt(right))
            return false;
        left ++;
        right --;
    }
    return true;
}

private boolean isAlphanumeric(char c) {
    return ('a' <= c && c <= 'z')
        || ('0' <= c && c <= '9');
}