Valid Palindrome

Difficulty:  🟢 Easy
Techniques:  2-PTR 
Links:  LeetCode  

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string str, return true if it is a palindrome, or false otherwise.

Maintain 2 pointers (one at start and one at end of string)


While they don't meet:
    Skip comparison if non-alphanumeric character.


    Compare if the lower-case form of the two characters are same:
        if not, return answer as NOT Palindromes.


    Move both pointers closer.
MetricComplexity
Time\( O(n) \) … one-pass over string’s characters
Space\( O(1) \)
bool isPalindrome (string str) {
    int n = str.size();
    int left = 0, right = n - 1;
    // While the two pointers don't meet
    while (left < right) {
        // Skipping comparison for non-alphanumeric characters
        if (!isalnum(str[left])) {
            left++;
            continue;
        }
        if (!isalnum(str[right])) {
            right--;
            continue;
        }
        // Lower-case form of the two characters not same
        if (tolower(str[left]) != tolower(str[right])) {
            return false;
        }
        // Move both pointers closer
        left++, right--;
    }
    return true;
}