612. A Palindrome If You Ignore the Rest
A single line of text is given. Consider only its LETTERS and DIGITS, treating upper and lower case as the same, and ignore everything else.
Print Yes if what remains reads the same forwards and backwards, and No otherwise.
A man, a plan, a canal: Panama -> Yes
race a car -> No
## The easy way, and why the sweep is better
Building a cleaned copy and comparing it with its reverse is correct and clear, and it uses
O(n) extra memory. The two-pointer version uses O(1) and is barely longer.
More usefully, it generalises: once you can skip characters that do not count, the same loop handles "ignore spaces", "ignore case only", or any other filter, without building anything.
## The sweep
i = 0, j = len-1
while i < j:
while i < j and s[i] is not alphanumeric: i += 1
while i < j and s[j] is not alphanumeric: j -= 1
if lower(s[i]) != lower(s[j]): answer No
i += 1; j -= 1
answer Yes
## The guard inside the skip loops
Both inner loops test i < j as well as the character. Without it, a string of nothing but
punctuation runs i off the end of the string and reads past it.
., is the test for exactly that, and it must answer Yes: after ignoring everything, what
remains is empty, and an empty sequence reads the same both ways.
## Reading the input
The line may contain SPACES, so it must be read as a whole line and not split on whitespace.
A reader that takes tokens sees A, man, and so on, and quietly solves a different problem.
The line is never empty, but it may be a single space.
## What counts as alphanumeric
Letters a-z and A-Z, and digits 0-9. Digits are not case-folded and compare as
themselves.
0P answers No: the cleaned string is 0p, and 0 is not p. That input catches
implementations that compare with a case-insensitive rule applied to digits, or that use a
letters-only filter and so see just P, which would answer Yes.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ length of the line ≤ 200000` - the line contains printable ASCII characters and no tab
Input
One line of text, which may contain spaces and punctuation. Its length is at least 1 and at most 200000.
Output
Print Yes or No on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.