125. Valid Palindrome

Problem¶

Given a string, ignore non-alphanumeric characters and case, then decide whether the remaining characters read the same forward and backward.

Example:

"A man, a plan, a canal: Panama" -> "amanaplanacanalpanama" -> True

Key trick¶

Use two pointers from both ends and skip non-alphanumeric characters on the fly.

This avoids building a cleaned copy.
It keeps space at \(O(1)\).

Trap¶

Common mistakes:

Forgetting to ignore punctuation and spaces.
Forgetting case-insensitive comparison.
Treating the empty cleaned string as False instead of True.
Building the cleaned string with regex when the interview expects the in-place two-pointer idea.

Why is it interesting?¶

It looks trivial, but it tests careful handling of normalization and a classic two-pointer scan.

Python solution¶

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Scan from both ends.
        # Skip non-alphanumeric chars and compare lowercase letters.
        l, r = 0, len(s) - 1

        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1

            if s[l].lower() != s[r].lower():
                return False

            l += 1
            r -= 1

        return True

Comment on my solution¶

Your solution is correct and clear.

Good:

Correct normalization.
Correct half-scan.
Good test starter.

Could be better:

if len(s) == 0: return True is unnecessary because the loop already handles it.
Regex creates a new string, so space is \(O(n)\) instead of \(O(1)\).
In interviews, the two-pointer version is usually the expected trick.
Add more edge cases like "0P", ".,", and mixed punctuation.

import pytest
import re

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # s = [a | mid_value | b]
        # s is a palindrom <=> s == [rev(b) | mid_value | rev(a)]
        # Since a = rev(b) => rev(a) = b, we can just test half of the string

        s = re.sub(r"[^a-z0-9]", "", s.lower())
        if len(s) == 0:
            return True
        for i in range(len(s) // 2):
            if s[i] != s[len(s) - 1 - i]:
                return False
        return True

class SolutionNoRegex:
    def isPalindrome(self, s: str) -> bool:
        # Implemented after reading comment from AI
        left = 0
        right = len(s) - 1
        while left < right:
            l = s[left].lower()
            r = s[right].lower()
            if re.match(r"[^a-z0-9]", l):
                left += 1
                continue
            if re.match(r"[^a-z0-9]", r):
                right -= 1
                continue
            if l != r:
                return False
            left += 1
            right -= 1
        return True

@pytest.mark.parametrize(
    ("s", "is_palindrome"),
    [
        ("A man, a plan, a canal: Panama", True), # "amanaplanacanalpanama"
        ("race a car", False), # "raceacar"
        (" ", True)
    ]
)
def test_isPalindrome(s, is_palindrome):
    assert SolutionNoRegex().isPalindrome(s) == is_palindrome
    assert Solution().isPalindrome(s) == is_palindrome