Valid Palindrome 415

Question

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.

Challenge

O(n) time without extra memory.

Solution

前后指针，用Character.isLetterOrDigit来判断是否是字符和数字。

代码如下：

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 false;
        }

        if(s.length() == 0){
            return true;
        }

        s = s.toLowerCase();

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

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

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

        return true;
    }
}