Saturday, January 10, 2015

LeetCode 125: 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.
public class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        
        if (n == 0)
            return true;
        
        // Note: Upper case and lower case is identical for palindrome.
        s = s.toLowerCase();    
        int i = 0, j = n-1;
        
        while (i < j)
        {
            while (i<j && !isAlphaNum(s.charAt(i)))
                i++;
                
            while (i<j && !isAlphaNum(s.charAt(j)))
                j--;
                
            if (i >= j)
                break;
                
            if (s.charAt(i) != s.charAt(j))
                return false;
                
            i++;
            j--;
        }
        
        return true;
    }
    
    private boolean isAlphaNum(char c)
    {
        if (c>='0' && c<='9')
            return true;
            
        if (c>='a' && c<='z')
            return true;
            
        return false;
    }
}

No comments:

Post a Comment