## Thursday, February 21, 2013

### [LeetCode] Valid Palindrome, Solution

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.
» Solve this problem

[Thoughts]
Two pointer. From both sides to middle.

[Code]
1:       bool isPalindrome(string s) {
2:            int start = 0;
3:            int end = s.size()-1;
4:            std::transform(s.begin(), s.end(), s.begin(), ::tolower);
5:            while(start<end)
6:            {
7:                 while(start< end && !isAlpha(s[start])) start++;  //filter non-alpha char
8:                 while(start< end && !isAlpha(s[end])) end--;  //filter non-alpha char
9:                 if(s[start]!=s[end]) break;
10:                 start++;
11:                 end--;
12:            }
13:            if(start >= end)
14:                 return true;
15:            else
16:                 return false;
17:       }
18:       bool isAlpha(char c)
19:       {
20:            if(c>='a' && c<='z') return true;
21:            if(c>='0' && c<='9') return true;
22:            return false;
23:       }