[LintCode] 415 Valid Palindrome 解题报告

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.



Challenge
O(n) time without extra memory.




思路
左右两个指针往中间走。
如果碰到不是数字或字母的字符，就跳过。
比较是否相等，不是就return。
最后全部比完了，return true。



Code

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

        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (!isValid(s.charAt(i))) {
                i++;
                continue;
            }
            if (!isValid(s.charAt(j))) {
                j--;
                continue;
            }
            if (!Equal(s.charAt(i), s.charAt(j))) {
                return false;
            }
            i++;
            j--;
        }
        
        return true;
    }
    
    public boolean isValid(char c) {
        return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
    }
    
    public boolean Equal(char x, char y) {
        if (x >= '0' && x <= '9') {
            return x == y;
        }
        return (x == y) || (x + 'A' - 'a' == y) || (y + 'A' - 'a' == x);
    }
}