Google+ Followers

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:       }  


Post a Comment