Problem

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.

Solution

Solution 1

The easiest way to do this is to construct a new string with only alphanumeric characters

class Solution:
    def isPalindrome(self, s: str) -> bool:
        newStr = ""

        for i in s:
            if i.isalnum():
                newStr += i.lower()
        # The original string contains mixed-case chars 
        # and puncuation etc
        # we compare the newStr to itself in reverse
        # to see if its a palindrome
        return newStr == newStr[::-1]
        

We can do better with 2 pointers.

Solution 2

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # We can put 2 pointers on each end
        # pointer1 = 0
        # pointer2 = len(s)
        # while the pointers do not equal each other
        # if pointer1 or 2 is looking at a puncuation mark, move that pointer forward
        # else see if both chars match
        # if they do, move both pointers forward
        # else return False
        pointer1 = 0
        # we count from 0 in arrays
        pointer2 = len(s) - 1
        while pointer1 < pointer2:
            # we want to compare lowercase chars per the description
            p1Char = s[pointer1].lower()
            p2Char = s[pointer2].lower()
            # if its puncuation
            if not p1Char.isalnum():
                # increment to the right by one
                pointer1 += 1
            elif not p2Char.isalnum():
                # decrement to the left by one
                pointer2 -= 1
            else:
                # else both chars are alpha numeric
                if not p1Char == p2Char:
                    # if they do not match, return False
                    return False
                else:
                    # else increment / decrement
                    pointer1 += 1
                    pointer2 -= 1
        return True