Two pointers: valid palindrome
Two pointers: valid palindrome
A palindrome reads the same forwards and backwards. The catch in this
classic (LeetCode #125) is that we only care about alphanumeric characters,
and we ignore case. So "A man, a plan, a canal: Panama" counts as a
palindrome β strip the punctuation and spaces, lowercase it, and you get
amanaplanacanalpanama, which is a mirror of itself.
Brute force would build a cleaned string and compare it to its reverse. The slicker move is two pointers: one starting at the far left, one at the far right, walking toward the middle. Skip anything that isn't a letter or digit, then compare the characters you land on.
left, right = 0, len(s) - 1
while left < right:
# skip non-alphanumerics on each side, then compare
...
If the two pointers ever disagree, it's not a palindrome. If they cross without a single mismatch, it is.
Your task
Write is_palindrome(s) returning True if s is a palindrome when you
consider only alphanumeric characters and treat upper/lowercase as equal,
otherwise False.
is_palindrome("A man, a plan, a canal: Panama") # True
is_palindrome("race a car") # False
is_palindrome("") # True (nothing to fail)
is_palindrome(".,") # True (no alphanumerics)
Hint: c.isalnum() tells you whether c is a letter or digit, and
c.lower() normalizes case. An empty string β or one made entirely of
punctuation β is trivially a palindrome.
Tests
- classic phrase
- not a palindrome
- empty string
- only punctuation
- alphanumeric mix (hidden)
- single char (hidden)
Stuck? Ask for a spark
$ Console output will appear here.