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.

Solution:

就是从两头出发，往中间走，进行两两匹配。这里面的小问题就是在这个题目要求中，只判断字母和数字类型的字符，其他字符直接跳过即可。因此我们要写一个函数判断他是不是合法字符，而且因为忽略大小写，我们在判断两个字符是不是相同的时候如果是大写，要转成相应的小写字母。这个算法从两边扫描，到中间相遇，只需要一次线性扫描，复杂度是O(n)，空间上是O(1)。

public class Solution {
    public boolean isPalindrome(String s) {
        if(s == null || s.length() == 0)
            return true;
        
        int l = 0, r = s.length() - 1;
        while(l < r) {
            if(Character.isLetterOrDigit(s.charAt(l)) && Character.isLetterOrDigit(s.charAt(r))) {
                if(s.charAt(l) == s.charAt(r) || s.charAt(l) + 32 == s.charAt(r) || s.charAt(r) + 32 == s.charAt(l)) {
                    l++;
                    r--;
                } else
                    return false;
            }else if(!Character.isLetterOrDigit(s.charAt(l))) {
                l++;
            }else if(!Character.isLetterOrDigit(s.charAt(r))) {
                r--;
            }
        }
        return true;
    }
}

public class Solution {
public boolean isPalindrome(String s) {
        if(s.length() == 0 || s.length() == 1)
            return true;
        else if(s == null)
            return false;
           
        int i = 0;
        int j = s.length() - 1;

        while(i < j) {
            char first = s.charAt(i);
            char last = s.charAt(j);

            while(i < s.length() - 1 && !isAlpha(first) && !isNum(first)) {
                i++;
                first = s.charAt(i);
            }
            while(j > 0 && !isAlpha(last) && !isNum(last)) {
                j--;
                last = s.charAt(j);
            }
            if(i > j)
                break;
            
            if(!isSame(first, last))
                return false;
            
            j--;
            i++;
        }
        return true;
    }
    
    public boolean isAlpha(char a) {
        if((a >= 'A' && a <= 'Z') || (a >= 'a' && a <= 'z'))
            return true;
        else
            return false;
    }
    
    public boolean isNum(char a) {
        if(a >= '0' && a <= '9')
            return true;
        else 
            return false;
    }
    
    public boolean isSame(char x, char y) {
        if(Character.toLowerCase(x) == Character.toLowerCase(y))
            return true;
        else if(isNum(x) && isNum(y)) {
            return x == y;
        }else
            return false;
    }
}

O(n) runtime, O(1) space: The idea is simple, have two pointers – one at the head while the other one at the tail. Move them towards each other until they meet while skipping non-alphanumeric characters. Consider the case where given string contains only non-alphanumeric characters. This is a valid palindrome because the empty string is also a valid palindrome.

public class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        
        while(i < j) {
            while(i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
            while(i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
            
            if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                 return false;
            }
            
            i++;
            j--;
        }
        return true;
    }
}