Return true if the string is a palindrome, considering only alphanumeric
characters and ignoring case. Spaces, punctuation, and case differences don't
count.
isPalindrome(s)
Input format: a single line (may contain spaces and punctuation).
"A man, a plan, a canal: Panama" // → true
"race a car" // → false
" " // → true (no alphanumerics)
A palindrome reads the same forwards and backwards. The natural first instinct: strip non-alphanumerics, lowercase what's left, and compare to its own reverse. That works, but it means building new strings and multiple passes for something that doesn't need them.
A palindrome check is really: does position 0 match the last position, position 1 match the second-to-last, and so on inward? You never need a reversed copy — just compare the first unprocessed character to the last, repeatedly, until you run out of pairs.
Put one pointer at the start, one at the end. Compare. If they match, move both inward and repeat. If they meet or cross with no mismatch, it's a palindrome. The moment a pair doesn't match, stop and return false.
This does the work in one pass, using no storage proportional to input size — just two positions — and bails out the instant a mismatch appears, rather than always building a full reversed copy first.
Punctuation, spaces, and case shouldn't count. Fold that into the pointer movement itself: before comparing, advance the left pointer past any non-alphanumeric character, and pull the right pointer backward past any non-alphanumeric character. Once both sit on real characters, compare case-insensitively. Skipping and comparing happen in the same pass — no separate cleanup step.
Every character needs to be looked at least once — there's no way to verify a palindrome without examining the whole string (or bailing early on a mismatch). Two pointers hit that lower bound using only constant extra space, better than any approach needing a full second copy.
def is_palindrome(s):
def is_alnum(ch):
return ("a" <= ch <= "z") or ("A" <= ch <= "Z") or ("0" <= ch <= "9")
left = 0
right = len(s) - 1
while left < right:
while left < right and not is_alnum(s[left]):
left += 1
while left < right and not is_alnum(s[right]):
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.