Valid Palindrome
Easy· opposite ends
Problem
Ignoring case and every character that is not a letter or digit, decide whether a string reads the same forwards and backwards.
Examples
Input: s = "Was it a car or a cat I saw?"
Output: true
After cleaning it becomes "wasitacaroracatisaw", which is a palindrome.
Input: s = "race a car"
Output: false
Constraints
- • 1 <= s.length <= 2 * 10^5
- • s consists of printable ASCII characters
Hints & approach
Hint 1
You could build a cleaned copy, but you do not have to.
Hint 2
Put one pointer at each end and move them inward, skipping characters that do not count.
Approachtry the hints first
Place left at the start and right at the end. Advance left past non-alphanumeric characters and retreat right likewise. Compare the two characters case-insensitively; on a mismatch return false, otherwise move both inward. If the pointers cross without a mismatch, the string is a palindrome.
Time O(n) · Space O(1)