sundeepblue
5/4/2014 - 6:58 PM

## [string] valid palindrome, leetcode

[string] valid palindrome, leetcode

``````/*
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.
*/

char to_upper(char c) {
if('a' <= c && c <= 'z')
c -= 'a' - 'A';
return c;
}

bool is_valid(char c) {
if('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9') return true;
return false;
}

bool isPalindrome(string s) {
int n = s.size();
if(n == 0) return true;
if(n == 1) return true;
int left = 0, right = n-1;
while(left < right) {
if(is_valid(s[left]) == false) { left++; continue; }
if(is_valid(s[right]) == false) { right--; continue; }
if(to_upper(s[left]) != to_upper(s[right]))
return false;
left++;
right--;
}
return true;
}

bool isPalindrome( string s) {
if(s.empty()) return true;
int low = 0, high = s.size()-1;
while(low < high) { // either <= or < is ok
while(low < high && !is_valid(s[low])) low++;
// if(low > high) return true;
while(low < high && !is_valid(s[high])) high--;
if(to_upper(s[low]) != to_upper(s[high]))
return false;
low++;
high--;
}
return true;
}``````