Valid Palindrome

Intuition

A palindrome is symmetric, so the character we meet coming from the front should match the character we meet coming from the back. Instead of building a filtered copy of the string, we can move two indices toward the middle and simply hop over characters we are told to ignore. Whenever both pointers land on real letters or digits, they must agree after lowercasing; the first disagreement proves the string is not a palindrome.

Algorithm walkthrough

1. 1Place a left index at the start of the string and a right index at the last position.
2. 2Advance the left index while it points at a non-alphanumeric character, and pull the right index back while it points at a non-alphanumeric character.
3. 3Compare the two characters after converting both to lowercase; if they differ, return false immediately.
4. 4Otherwise step the left index forward and the right index backward and repeat.
5. 5When the two indices meet or cross, every pair matched, so return true.

Implementation

class Solution:
    def isPalindrome(self, s: str) -> bool:
        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