Problem:

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.

 

Analysis:

Get two pointer pi, pj, pi points to the head of the string, pj points to the end of the string. 

Then compare the two pointed characters, if they are the same, then pi++, pj--, repeat the comparision.

If they are not the same, return false;

 

Code:

1 class Solution { 2 public: 3     bool isPalindrome(string s) { 4         // Start typing your C/C++ solution below 5         // DO NOT write int main() function 6         if (s == "") return true; 7          8         int i = 0, j = s.size()-1; 9         while (true) {10             while (!((s[i]>='0'&&s[i]<='9') || (s[i]>='a' && s[i]<='z')11                     || (s[i]>='A' && s[i]<='Z')))12                     if ((i++) >= s.size()) break;13                     14             while (!((s[j]>='0'&&s[j]<='9') || (s[j]>='a' && s[j]<='z')15                     || (s[j]>='A' && s[j]<='Z')))16                     if ((j--) < 0) break;17                     18             if (i >= j) break;19             20             if (toLower(s[i]) != toLower(s[j]))21                 return false;22             23             i++;24             j--;25         }26         27         return true;28     }29     30     char toLower(char a) {31         if (a>='A' && a<= 'Z')32             a += 32;33             34         return a;35     }36     37     38 };

 

Attention: