Question：

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.

Anwser 1：

class Solution {
public:
    bool isStr(char &ch){
        if(ch >= '0' && ch <= '9'){
            return true;
        } else if(ch >= 'a' && ch <= 'z'){
            return true;
        } else if(ch >= 'A' && ch <= 'Z'){
           ch += 32;
           return true;
        } 
        
        return false;
    }
    
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len = s.length();
        if(len == 0){
            return true;
        }
        
        string str = "";
        for(int i = 0; i < len; i++){   // remove illegal char, such as "?" "/" ...
            if(isStr(s[i])){
                str += s[i];
            }
        }
        
        len = str.length();
        int mid = (len + 1) / 2;
        for(int i = 0; i < mid; i++){
            if(str[i] != str[len - 1 - i]){     // check front and end char
                return false;
            }
        }
        return true;
    }
};

Anwser 2：

class Solution {
public:
    bool isStr(char &ch){
        if(ch >= '0' && ch <= '9'){
            return true;
        } else if(ch >= 'a' && ch <= 'z'){
            return true;
        } else if(ch >= 'A' && ch <= 'Z'){
           ch += 32;
           return true;
        } 
        
        return false;
    }
    
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len = s.length();
        if(len == 0){
            return true;
        }
        
        int i = 0;
        int j = len - 1;
        while(i < j){
            if(!isStr(s[i])) {
                i++;
            } else if(!isStr(s[j])) {
                j--;
            } else if(s[i++] != s[j--]) {
                return false;
            }
        }
        
        return true;
    }
};

注意点：

1） 字母数字判断，注意字母中的字母大小写转换（把大写加32全部转化成小写）

2） 方法2中采用判断删除的方法，效率要高，且不占用另外字符串存储（str）