Valid Palindrome

Problem

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

A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

Note: Alphanumeric characters consist of letters (A-Z, a-z) and numbers (0-9).

Examples

Example 1:

Input: s = "Was it a car or a cat I saw?"

Output: true

Example 2:

Input: s = "tab a cat"

Output: false

Constraints

• 1 <= s.length <= 1000
• s is made up of only printable ASCII characters.

You should aim for a solution with O(n) time and O(1) space, where n is the length of the input string.

Solution

Check end points for equality, and move inward.

class Solution {
public:
    bool isPalindrome(string s) {
        // Start from either side, compare, and walk in sync.
        for (std::size_t i = 0; i < s.size() / 2; ++i) {
            if (s[i] != s[s.size() - i]) {
                return false;
            }
        }
        return true;
    }
};