https://leetcode.com/problems/valid-palindrome/

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 s, return true if it is a palindrome, or false otherwise.

Idea:

Two pointers

Solution:

class Solution {
public:
    bool isPalindrome(string &s) {
        for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {            
            nextLetter(s, i, j);

            if (tolower(s[i]) != tolower(s[j])) {
                return false;
            }
        }

        return true;
    }

    void nextLetter(const string &s, int &i, int &j) {
        while (i < j && !isalnum(s[i])) {
            i++;
        }
        while(i < j && !isalnum(s[j])) {
            j--;
        }
        
    }
};

Complexity Analysis:

Time

O(N) one pass over the string

Memory

O(1) constant memory for loop variables