125. Valid Palindrome

Reformulated question¶

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 this question interesting?¶

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

Solve the problem with idiomatic python¶

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

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

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

Library-based alternative:

import re

class SolutionRegex:
    def isPalindrome(self, s: str) -> bool:
        # Simple and readable, but uses extra memory for the cleaned string.
        cleaned = re.sub(r"[^a-z0-9]", "", s.lower())
        return cleaned == cleaned[::-1]

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("s", "expected"),
    [
        ("A man, a plan, a canal: Panama", True),
        ("race a car", False),
        (" ", True),
        ("0P", False),
        ("aa", True),
        ("ab", False),
        ("a.", True),
        (".,", True),
        ("Madam", True),
        ("No 'x' in Nixon", True),
    ],
)
def test_is_palindrome(s, expected):
    assert Solution().isPalindrome(s) is expected

Comment 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