# 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