valid_palindrome.py

class Solution:
    """LeetCode #125 - Valid Palindrome (Easy)
    https://leetcode.com/problems/valid-palindrome/

    A phrase is a palindrome if, after removing every non-alphanumeric character
    and lowercasing the rest, it reads the same forwards and backwards.
    """

    def is_palindrome_cleanup(self, s: str) -> bool:
        """First approach: clean the string, then compare it with its reverse.

        Very readable, and it is what most people write first. The cost is an
        extra copy of the string.

        Time:  O(n) - one filtering pass plus the slice comparison.
        Space: O(n) - the cleaned copy.
        """
        cleaned = [ch.lower() for ch in s if ch.isalnum()]
        return cleaned == cleaned[::-1]

    def isPalindrome(self, s: str) -> bool:
        """Optimal approach: two pointers walking toward each other.

        Key insight: we do not need to build a cleaned string at all. Keep one
        pointer at each end, skip anything that is not alphanumeric, and compare
        the two characters that actually matter. The pointers meet in the middle
        after at most n steps in total.

        Time:  O(n) - each pointer only ever moves forward/backward.
        Space: O(1) - nothing but two integers.
        """
        left, right = 0, len(s) - 1

        while left < right:
            # Skip junk from the left, but never run past the right pointer.
            while left < right and not s[left].isalnum():
                left += 1
            # Same from the right side.
            while left < right and not s[right].isalnum():
                right -= 1

            if s[left].lower() != s[right].lower():
                return False                # mismatch -> not a palindrome

            left += 1
            right -= 1

        return True                          # pointers crossed, all pairs matched