Valid Palindrome(lintcode 415)

Description

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

Notice:
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.

Example

"A man, a plan, a canal: Panama" is a palindrome.

"race a car" is not a palindrome.

Interface

public class Solution {
    /**
     * @param s A string
     * @return Whether the string is a valid palindrome
     */
    public boolean isPalindrome(String s) {
        // Write your code here
    }
}

Idea

Use two indexes to compare the first and last characters in the string. If they are the same, we remove the indexes and compare the second and the second to last characters. Until the indexes meet each other we can make sure the string is a palindrome.

Solution

public class Solution {
    /**
     * @param s A string
     * @return Whether the string is a valid palindrome
     */
    public boolean isPalindrome(String s) {
        // Write your code here
        if (s == null) {
            return true;
        }

        int i = 0, j = s.length() - 1;
        s = s.toLowerCase();
        while (i < j) {
            while (!Character.isLetterOrDigit(s.charAt(i)) && i < j) {
                ++i;
            }

            while (!Character.isLetterOrDigit(s.charAt(j)) && j > i) {
                --j;
            }

            if (i == s.length() - 1 && j == 0 && !Character.isLetterOrDigit(s.charAt(i)) && !Character.isLetterOrDigit(s.charAt(j))) {
                return true;
            }

            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }

            ++i;
            --j;
        }

        return true;
    }
}