Is this a palindrome, ignoring punctuation and case?

Question

Given a phrase, decide whether it is a palindrome when you consider only its letters and digits and treat uppercase and lowercase as equal.

"A man, a plan, a canal: Panama"  -> True
"race a car"                      -> False
""                               -> True

Return a boolean in $O(n)$ time and $O(1)$ extra space. Do not build a cleaned copy of the string; scan in place.

Accepted Answer

Keep two pointers, one at each end, and move them inward. Whenever a pointer sits on a character that is not a letter or digit, skip it without comparing. When both pointers rest on real characters, compare them case-insensitively; a mismatch means it is not a palindrome. If the pointers cross without ever mismatching, it is. Tracing "A man, a plan, a canal: Panama": after lowercasing and skipping spaces and punctuation the pointers compare a/a, m/m, a/a, and so on inward, never mismatching, so the function returns True. For "race a car" the outer pair r/r matches but the pointers soon reach …

Is this a palindrome, ignoring punctuation and case?

Your answer

More Coding questions