LeetCode 125. Valid Palindrome

LeetCode 125. Valid Palindrome

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

Matter

You are given a string that may contain letters, digits, spaces, and symbols.

Determine whether it becomes a palindrome after:

• ignoring all non-alphanumeric characters
• converting all letters to lowercase

Return true if it reads the same forward and backward, otherwise return false.

Example.

[1] Input:
s = "A man, a plan, a canal: Panama"

Output:
true

Explanation:
After filtering and normalization → "amanaplanacanalpanama"

[2] Input:
s = "race a car"

Output:
false

Explanation:
Filtered string → "raceacar" → not symmetric

[3] Input:
s = " "

Output:
true

Explanation:
After removing invalid characters → empty string → valid palindrome

Constraints

1 <= s.length <= $2 \times 10^5$

The string contains printable ASCII characters.

Problem analysis

The problem is not just checking a palindrome directly.

We must:

1. Skip invalid characters
2. Compare characters in a case-insensitive way

Key Idea

Use two pointers

• One pointer from the left
• One pointer from the right

Move both inward while:

• skipping non-alphanumeric characters
• comparing lowercase values

Why Two Pointers?

• Avoid extra memory
• One pass solution
• Efficient for large input size

Miss Check list

• Must ignore non-alphanumeric characters
• Must convert uppercase to lowercase before comparing
• Empty string is valid
• Do not create unnecessary copies if possible

Solution

Two Pointer Approach

class Solution 
{
public:
    bool isPalindrome(std::string s) 
    {
        int i32Left = 0;
        int i32Right = s.size() - 1;
        bool bIsPalindrome = true;

        while(i32Left < i32Right)
        {
            while(i32Left < i32Right && !isalnum(s[i32Left]))
                i32Left++;

            while(i32Left < i32Right && !isalnum(s[i32Right]))
                i32Right--;

            bIsPalindrome = tolower(s[i32Left]) == tolower(s[i32Right]);
            i32Left++;
            i32Right--;

            if(!bIsPalindrome)
                break;
        }

        return bIsPalindrome;
    }
};

Compare all

class Solution 
{
public:
    bool isPalindrome(std::string s) 
    {
        std::vector<char> vctString;

        for_each(s.begin(), s.end(), 
        [&vctString](char i8Char)
        {
            char i8Lower = std::tolower(i8Char);

            if(std::isalnum(i8Lower))
                vctString.push_back(i8Lower);
        });

        std::vector<char> vctStringRev(vctString);
        std::reverse(vctStringRev.begin(), vctStringRev.end());

        return vctString == vctStringRev;
    }
};