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
true if it is a palindrome, or
Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.
Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.
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.
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.
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