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