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.

class Solution {public:bool isValid(char c){    if((c>='a'&&c<='z')||(c>='A'&&c<='Z')||(c>='0'&&c<='9'))return true;    return false;}bool isSame(char c1, char c2){    if(c1>='0'&&c1<='9')return c1==c2;    if((c1>='A'&&c1<='Z'))return (c1==c2)||(c1==c2-32);    if(c1>='a'&&c1<='z')return (c1==c2)||(c1==c2+32);}    bool isPalindrome(string s) {        if(s.empty()||s.size()==1)return true;        int n=s.size();        int i=0,j=n-1;        for(;i
     
      =0&&i<=j;)        {//            if(i==j)return true;            while(!isValid(s[i]))i++;            while(!isValid(s[j]))j--;            if(i==j||i>j)return true;            if(!isSame(s[i],s[j]))return false;            i++;            j--;        }        if(i==j||i>j)return true;        return false;    }};