1/27/2013

Valid Palindrome

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.

class Solution {
public:
    inline bool isValidChar(char &c) {
        if (c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
            return true;
        }
        else {
            return false;
        }
    }
    
    inline bool isLetter(char &c) {
        if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
            return true;
        }
        else {
            return false;
        }
    }
    
    inline bool compare(char &c1, char &c2) {
        if (c1 == c2 || isLetter(c1) && isLetter(c2) && abs(c1 - c2) == 32) {
            return true;
        }
        else {
            return false;
        }
    }
    
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = 0, j = s.size() - 1;
        while (i < j) {
            while (i < j && !isValidChar(s[i])) ++i;
            while (i < j && !isValidChar(s[j])) --j;
            if (i < j) {
                if (!compare(s[i], s[j]))
                    return false;
            }
            ++i;
            --j;
        }
        return true;
    }
};

No comments:

Post a Comment