[LeetCode Road] Valid Palindrome - Solution/C++

125. Valid Palindrome

Question:

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example:

Input: "A man, a plan, a canal: Panama"
Output: true

Input: "race a car"
Output: false

Constraints:

s consists only of printable ASCII characters.

Source code

Version 1

Idea:
You can easily solve the problem by the library function.
However, you must understand the description of question, "Palindrome" means that characters of string are the same when you read it forwards from the beginning or backwards from the end.

"alphanumeric" the content of question is a key point, you should consider alpha and numeric together（Ignor punctuation marks and whether alpha is uppercase or lowercase or not).
So, you shoud call isalnum rather than isalpha to filter characters of string.

head < tail condition is very important, e.g., input= ".," Initial: head = 0 & tail=1
At 7 line, while() will break when head is added 1(. is not alphanumeric).
At 8 line, while() is break direcly, because head = tail (both variables are 1)
At 10 line, IF statement will get true and break out of a outer loop.

Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    bool isPalindrome(string s) {
        int head = 0;
        int tail = s.length() - 1;
        while(head < tail){
            while(head < tail && !isalnum(s[head])) head++;
            while(head < tail && !isalnum(s[tail])) tail--;
            
            if(tolower(s[head]) != tolower(s[tail])) return false;
            head ++;
            tail --;
        }
        return true;
    }
};