Valid Palindrome
Valid Palindrome is an easy Two Pointers problem from the Blind 75. The key pattern is two pointers, and a good solution runs in O(n) time.
Problem
Ignore non-alphanumeric characters and letter case, then determine whether the remaining text is a palindrome.
Examples
Example 1
Input
"Was it a rat I saw?"Output
trueExample 2
Input
"Step on no pets!"Output
trueExample 3
Input
" "Output
trueApproach
Move one pointer from each end, skip characters that are not letters or digits, and compare the rest case-insensitively until the pointers meet.
| Pattern | Two pointers |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
A string with no alphanumeric characters is a palindrome.